Technical Reports
HPL-2010-176
Click here for full text:
Maintaining the Ranch topology
Li, Xiaozhou; Misra, Jayadev; Plaxton, Greg
HP Laboratories
HPL-2010-176
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]