On the Convergence of Chord Network

Due to the churn, the P2P overlay network can not be static. The dynamic environment may degrade the services provided by distributed hash table (DHT), then the convergence of the overlay is very important. In this paper, we try to analyze the convergence of Chord network. We prove that the generic structures of Chord network is a pseudo-tree, which can be converged to a circle by algorithm stabilize. The ring in Chord has more meanings than a circle in graph theory, and the ring requires all nodes in the network permuted by their ids. An efficient strong_stabilize algorithm is proposed to make the network converge to a ring rapidly.