Chord notes

- Directory
      * key-value pairs
      * no structure on the keys
      * no special servers

- Consistent hashing
      * m-bit hash output, ring from 0 to 2^m-1
      * hash(key) and hash(nodeid)
      * key stored at successor node on the ring
      * assumes every node knows about every other node
      * minimizes disruption when a node joins/leaves the ring

- Simple key location
      * each node knows its successor on the ring
      * sequence along the ring from each node to its successor
      * stop when a pair of nodes straddle hash(key)
      * the second node is responsible for the key
      * ... can store the key-value pair at each of the k nodes after the key

- Successors
      * next node in the ring
      * or, for better reliability, the next r nodes in the ring

- Finger table
      * i-th entry is first node at least 2^{i-1} away on the ring
      * node n searches finger table for node most immediately preceding id
      * ... and then this node does the same, and repeat, ...
      * each node can forward a query at least halfway along the remaining 
           distance between the node and the target identifier
      * ... so, need to contact at most log(N) nodes
      * note that distance halving depends only on id-space distances, so missing
            some new nodes doesn't significantly affect look-up speed

- Dynamics
      * New node n joins
           - calling n.join(n') for any known n' in the ring
           - node n' is asked to find the immediate successor of n
      * Every node periodically runs stabilize
           - node n asks its successor for the successor's predecessor p
           - node n decides whether p should be n's successor instead
           - stabilizing also lets n's successor know about n's existence, giving the
                 successor the chance to change its predecessor to n

Pamela's insight
- small rings are a problem
     * multiple successors in the successor list are the same node
     * if that node (or nodes) fail, the remaining nodes cannot find each other
     * (see figure 3 in the PODC submission)
     * Chord network must be initialized and maintained with a minimum ring size of r+1