I'm looking at the pseudocode for chord algorithm here:

// create a new Chord ring.
    predecessor := nil
    successor := n

// join a Chord ring containing node n'.
    predecessor := nil
    successor := n'.find_successor(n)

// called periodically. n asks the successor
// about its predecessor, verifies if n's immediate
// successor is consistent, and tells the successor about n
    x = successor.predecessor
    if x ∈ (n, successor) then
        successor := x

// n' thinks it might be our predecessor.
    if predecessor is nil or n'∈(predecessor, n) then
        predecessor := n'

// called periodically. refreshes finger table entries.
// next stores the index of the finger to fix
    next := next + 1
    if next > m then
        next := 1
    finger[next] := find_successor(n+{\displaystyle 2^{next-1}}2^{next-1});

// called periodically. checks whether predecessor has failed.
    if predecessor has failed then
        predecessor := nil

I'm struggling to make sense of it. My question specifically is: when exactly will the predecessor field EVER be non-null?

Consider a case where a node id 1 joins. Its successor is 1, the predecessor is nil.

Now say node with 10 joins. Its successor is 1, predecessor is nil.

The stabilization routine depends on the predecessor being non-nil, which in this case it isn't both nodes.

So how does the algorithm proceed at this point?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.