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.

Improve this question
$\endgroup$
1
  • 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. ♦
    Commented Jan 17, 2017 at 0:51

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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