0
$\begingroup$

I'm trying to understand Chord algorithm (for Peer-to-Peer systems) but I can't understand how it maps the documents to the nodes.

I have one example where we have:

  • keys with 4 bits
  • 5 active nodes with the following identifiers: 1, 5, 7, 10, 13

After mapping the documents to the nodes, we have:

Key 0 - Node 1

Key 2 - Node 5

Key 8 - Node 10

Key 11 - Node 13

Key 15 - Node 1

If somebody could help me with the steps that lead to this results I'd be truly grateful.

$\endgroup$

closed as unclear what you're asking by jmite, Yuval Filmus, David Richerby, Evil, Juho Jan 25 '17 at 8:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Welcome to CS.SE! What research have you done? What resources have you read? Chord is described in a bunch of places. $\endgroup$ – D.W. Jan 17 '17 at 0:51
1
$\begingroup$

Chord implementations use a defined function which is used to map the key identifiers (0, 2, 8, 11, 15 in your case) to the node identifiers (1, 5, 7, 10, 13). In the example you provided, the function works like this:

NodeID = KeyID % N

where NodeID is the (identifier) node where the key will be inserted, KeyID is the identifier of the key to be inserted, and N is the total number of nodes.

After you calculate the NodeID, it might be the case that this NodeID does not exist. For example, when KeyID is 0, the NodeID will be 0. Since NodeID doesn't exist, it will be allocated to the next highest (existing) node identifier which is NodeID = 1.

The keys identifier can be calculated using some hash algorithm.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.