In a Chord ring using m = 8, nodes with the following peer ids (or node ids) join the system: 45, 32, 132, 234, 99, 199. When all finger tables and successors have converged, what is the comma-separated list of nodes traversed by a query originating from node 45 intended for the key 12 (include both originating node and final node)?

Answer:

45,132,199

Where the successor is computed by the rule that we add 2^i to the value and take modulus 2^m of the resultant sum. i varies from 0 to m-1

So the expression is succ(n) = (n+2^i) mod (2^m) and the next valid node >=succ(n) is used as the successor

Hence we have the Finger table as given below for node 45

succ(46) = 99

succ(47) = 99

succ(49) = 99

succ(53) = 99

succ(61) = 99

succ(77) = 99

succ(109) = 132

For node 99 it is

So for the key 12 it will check the successor table and will move to the max node possible as 12 is not in its finger table hence it will move to 132

Then it will look into the table of 132 which is

succ(133) = 199

succ(134) = 199

succ(136) = 199

succ(140) = 199

succ(148) = 199

succ(164) = 199

succ(196) = 199

succ(4) = 32 (Here we are calculating succ(4) as 132 + 2^7 = 132+128 = 260 and 260 mod 256 = 4)

So here in this case we look at the highest predecessor to the key 12 which is 199 in this case hence we move to 199 and look at the finger table to move to 199

After this we check successor of 199 but 12 is not there hence the search ends

So the sequence of search is

45, 132, 199

PFA