# Extra 2: Chord Algorithm Berkeley CS 162

• Consistent Hashing
• ring space of $$0$$ to $$2^m - 1$$

• take an id like ip, hash it and put it on the ring
• in our key value store, where to store keys?
• node 20 knows key-values for [16, 20] since the previous node is at 15

• correctness
• because it is a ring!
• always a node that hold they keys
• performance
• $$O(log(n))$$

• routing
• start at any node which will contain where the next node is
• worst case is $$O(n)$$ - not great

• correctness with stabilization algorithm

• a new node gets one node from DNS
• it calls another node, which calls another node, etc.
• the final node connects to the new node and updates its successor as the new node

• finger table
• a table that knows probabilisticly approximately halfway, quarter, eighth, etc.
• now instead of having to hope each node
• you can jump at most half way, then another quarter, etc.
• $$\text{key}+2^i ~ \text{mod} ~ \text{ringsize}$$

• fault tolerance if the node fails, successor and precessor has a copy!

• Dynamo used Chord's Consistent Hashing but using a SLA agreement