Maintaining the Ranch topology

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.

Research highlights
► Ranch is a ring-based structured peer-to-peer network topology.
► A maintenance protocol is presented for Ranch.
► The protocol is efficient, performs full maintenance, and is highly concurrent.
► It is the first such protocol for any structured peer-to-peer network.