Maintaining the Ranch topology

Li, Xiaozhou ; Misra, Jayadev ; Plaxton, Greg

HP Development Company

关键词: Structured peer-to-peer networks;    Maintenance protocols;    Concurrency;    Correctness;   

RP-ID  :  HPL-2010-176

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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.