Merging and Splitting Structured Peer-to-Peer Systems

Peer-to-peer (P2P) systems can be classified into two categories: unstructured and structured. A crucial requirement for practical structured P2P systems is that they should be able to cope with system splitting and merging. To address this issue, we first present a randomized and fault-tolerance broadcast algorithm called RBA. It can inform all nodes in P2P system of splitting or merging. We analyze its upper bound and show that it can be easily implemented on Chord without extra cost. Then we present our distributed splitting and merging protocols for structured P2P systems. It searches correct fingers rather than simply reconstructing fingers as previous protocols do. Compared with previous protocols, our protocols perform faster and reduce the cost of splitting and merging P2P systems dramatically. The performances of our algorithms have been evaluated using both theoretical analysis and simulation.