Technical Reports


Click here for full text: PDF

Maintaining the Ranch topology

Li, Xiaozhou; Misra, Jayadev; Plaxton, Greg
HP Laboratories


Keyword(s): Structured peer-to-peer networks; Maintenance protocols; Concurrency; Correctness

Abstract: Topology maintenance, or how to handle the possibly concurrent joining and leaving of nodes, is a central problem for structured peer-to-peer networks. A good topology maintenance protocol should run efficiently, fully maintain the topology, and should not unduly restrict concurrency. In this paper, we present such a protocol for a multi-ring topology called Ranch. The protocol is efficient: for each join or leave, it uses a logarithmic number of messages with high probability. The protocol fully maintains Ranch after joins and leaves, and allows for a high degree of concurrency. To our knowledge, this is the first maintenance protocol that enjoys all of these properties for a structured peer-to-peer network topology.

37 Pages

Additional Publication Information: Published in Journal of Parallel and Distributed Computing, Vol. 70, Num. 11, Nov. 2010.

External Posting Date: November 21, 2010 [Fulltext]. Approved for External Publication
Internal Posting Date: November 21, 2010 [Fulltext]

Back to Index