question archive In a Chord ring using m = 8, nodes with the following peer ids (or node ids) join the system: 45
Subject:Computer SciencePrice:2.87 Bought7
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. If node 45 fails, then what is the comma-separated list of all the nodes whose finger tables need to be updated?
Answer:
Before we answer we need to understand the following.
-In an m-bit identifier space, there are 2m identifiers. Here m=8 means 28=64 identifies.
-Identifiers are ordered on an identifier circle modulo 2m.
-The identifier ring is called Chord ring.
-Key k is assigned to the first node whose identifier is equal to or follows (the identifier of) k in the identifier space.
-This node is the successor node of key k, denoted by successor(k).
-Each node n’ maintains a routing table with up to m entries (which is in fact the number of bits in identifiers), called finger table.
Since we have m=8, which means each Node i would be having 8 entries in its finger table denoting the 8 successors for that keys from (20 to 28)
-Key K is assigned to node whose identifier is >= Key.
Ex:Finger table for node 32
Keys | Successor Node
N32+20=32
N32+21=45
N32+22=45
N32+23=45
N32+24=45
N32+25=99
N32+26=99
N32+27=99
So likewise we can create the finger tables for the rest of the nodes (45,99,132,199,234)
Now if the node 45 is removed, we see that Node 45 is mentioned only as a finder table entries in only Node 32.
So the answer is 32.