Stabilization of Successor and Predecessor in Chord

1. Introduction

Chord is one of the most famous algorithms for a distributed hash table. In this article, I note the stabilization of Chord about successors and predecessors. Understanding stabilizations like Chord's one is important for understanding cloud computing :)
I don't note the stabilization of fingertable in this time and will note it in the other article :)

2. Stabilization of Successor and Predecessor

2.1. Logic of Stailization

The logic of the stabilization of successors and predecessors is as follows. In this figure, ID is the hash value of the node's IP address and port. The distance of nodes is the difference in IDs. So, the distance between 'Node A' and 'Node B' is as follows.

・Distance between 'Node A' and 'Node B'

ID of 'Node B' - ID of 'Node A'

(ID: the hash value of the node's IP address and port) 

2.2. Specific Example of Stabilization

Let's assume that the following ring in which blue nodes participate exists and has a pink node participate in the ring.
The successor of 'Node A' is incorrect, the predecessor of 'Node AA' is not assigned and the predecessor of 'Node B' is incorrect.

'Node AA' asks wheter the predecessor of his current successor ('Node B') is himself ('Node AA').
Because the predecessor of 'Node B' is not 'Node AA', 'Node AA' askes 'Node C' wheter he is closer to 'Node B' than 'Node A' is. Node AA' is closer to 'Node B' than 'Node A', so the predecessor of 'Node B' is revised to be 'Node AA'.

Node A' asks whether the predecessor of his current successor ('Node B') is himself ('Node A').
Because the node that is closer to 'Node B' than himself is 'Node AA', 'Node A' change his successor to 'Node AA'. And then, 'Node A' teach 'Node AA' that the predecessor of 'Node AA' is himself. 'Node AA' set his predecessor to 'Node A'.

The ring is as follows at this time. All successors and predecessors of nodes are properly set :)

3. Conclusion

The stabilization of successors and predecessors of nodes is based on a simple logic noted in 2.1. Even if nodes are added or removed, the stabilization revises these successors and predecessors and ring is properly maintained.