Self-Stabilizing, Cost-Effective, and Fast-Convergent Structured Overlay Maintenance

In this paper we study the self stabilization of structured overlay maintenance in decentralized peer-to-peer (P2P) systems. Our study addresses a number of limitations of existing overlay maintenance protocols, such as the reliance on a continuously available bootstrap system, the assumption of a known system stabilization time, and the need to maintain large local membership lists. In particular, we present a precise specification for self-stabilizing overlay maintenance protocols, with additional requirement on messaging and local state costs. All properties of the specification are desired by applications, while together they prohibit protocols with the limitations existed in previous proposals. We then provide a complete protocol with proof showing that it satisfies the specification. Finally, we show how to improve our self-stabilizing protocol to significantly reduce topology convergence time.