A Tale of Many Networks: Splitting and Merging of Chord-like Overlays in Partitioned Networks

Peer-to-peer overlays define an approach to operating data management platforms, which are robust against censorship attempts from countries or large enterprises. The robustness of such overlays is endangered in the presence of national Internet isolations, such as was the case in recent years during political revolutions. In this paper, we focus on splits and, with stronger emphasis, on the merging of ring-based overlays in the presence of network partitioning in the underlying Internet due to various reasons. We present a new merging algorithm named the Ring Reunion Algorithm and highlight a method for reducing the number of messages in both separated and united overlay states. The algorithm is parallelized for accelerated merging and is able to automatically detect overlay partitioning and start the corresponding merging processes. Through simulations, we evaluate the new Ring Reunion Algorithm in its simple and parallelized forms in comparison to a plain Chord algorithm, the Chord–Zip algorithm, and two versions of the Ring-Unification Algorithm. The evaluation shows that only our parallelized Ring Reunion Algorithm allows the merging of two, three, and more isolated overlay networks in parallel. Our approach quickly merges the overlays, even under churn, and stabilizes the node contacts in the overlay with small traffic overhead.