●●●● ●●●● ●●●● ●●●● Chord state and Lookup( 2) ●●●● ●●●● inger table ● Each node knows m N8+1N14 N8+2N14 other nodes on the ring m=6 N8+4N14 N8+8N21 Successors: finger iof n N1 N8+16|N32 points to node at n+2/(or N8+32|N42 successo N56 lookup(K54)IN8 K54 ● Predecessor( or ring management) N51 O(log N)state per node N48○ N14 +16 Lookup is achieved by +32 following closest preceding fingers, then N42 successor N38 ●O(ogN)hops N32 Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 16 Chord State and Lookup (2) ⚫ Each node knows m other nodes on the ring ⚫ Successors: finger i of n points to node at n+2i (or successor) ⚫ Predecessor (for ring management) ⚫ O(log N) state per node ⚫ Lookup is achieved by following closest preceding fingers, then successor ⚫ O(log N) hops N1 N8 N14 N32 N21 N38 N42 N48 N51 N56 m=6 K54 2 m-1 0 N8+1 N8+2 N8+4 N8+8 N8+16 N8+32 N14 N14 N14 N21 N32 N42 Finger table +32 +16 +8 +4 +2 +1 lookup(K54)
●●●● ●●●● ●●●● ●●●● Chord Ring Management ●●●● ●●●● o For correctness Chord needs to maintain the following invariants For every key k, succ(k is responsible for k o Successor pointers are correctly maintained Finger table are not necessary for correctness o One can always default to successor-based lookup Finger table can be updated lazily Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 17 Chord Ring Management ⚫ For correctness, Chord needs to maintain the following invariants ⚫ For every key k, succ(k) is responsible for k ⚫ Successor pointers are correctly maintained ⚫ Finger table are not necessary for correctness ⚫ One can always default to successor-based lookup ⚫ Finger table can be updated lazily
●●●● ●●●● ●●●● ●●●● Joining the Ring ●●●● ●●●● Three step process ● Initialize a‖ I fingers of new node o Update fingers of existing nodes o transfer keys from successor to new node Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 18 Joining the Ring ⚫ Three step process: ⚫ Initialize all fingers of new node ⚫ Update fingers of existing nodes ⚫ Transfer keys from successor to new node