Correctness of DHT

[RyanKung]

FACT

1. Chord must be initialized with a ring containing a minimum of r +1 nodes, where r is the length of each node’s list of successors. In fact, to be proven correct, a Chord network must maintain a “stable base” of r + 1 nodes that remain members of the network throughout its lifetime.

2. The Chord Paper defined the maintenance and use of finger tables, which improve lookup speed by providing pointers that cross the ring like chords of a circle. Because finger tables are an optimization and they are built from successors and predecessors, correctness does not depend on them.

IMPROVEMENTS

1. Join Operator: Sync successor list from new successor. Add new remote action:

RemoteAction::FetchSuccessorList(Did)

After join operator, call FindSuccessor(did) and FetchSuccessorList(Did) immediately。

2. Stab Operator: For current implementation, we notify predecessor for successor updating. But on paper HMCC, It defined a new operation that fetch successor's predecessor and successor_list periodically. And instead of notify predecessor, It notify successors.

The loop is guaranteed to terminate before succList is empty, based on the assumption that successor lists are long enough so that each list contains at least one live node.

3. Rectify operator, In origin Chord paper the operator is so called check_predecessor.

ref: How to Make Chord Correct https://arxiv.org/pdf/1502.06461.pdf