CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays

Unstructured overlays form an important class of peer-to-peer networks, notably when content-based searching is at stake. The construction of these overlays, which is essentially a membership management issue, is crucial. Ideally, the resulting overlays should have low diameter and be resilient to massive node failures, which are both characteristic properties of random graphs. In addition, they should be able to deal with a high node churn (i.e., expect high-frequency membership changes). Inexpensive membership management while retaining random-graph properties is therefore important. In this paper, we describe a novel gossip-based membership management protocol that meets these requirements. Our protocol is shown to construct graphs that have low diameter, low clustering, highly symmetric node degrees, and that are highly resilient to massive node failures. Moreover, we show that the protocol is highly reactive to restoring randomness when a large number of nodes fail.Spyros Voulgaris is a PhD student in the Computer Systems department at the Vrije Universiteit Amsterdam. He received his MSc degree from the University of Michigan, Ann Arbor, and his BSc degree from the University of Patras, Greece. His research involves peer-to-peer systems, epidemic protocols, and ad-hoc networks. He is a scholarship recipient of the Greek State Scholarships Foundation (IKY) and the Alexander Onassis Foundation.Daniela Gavidia is a PhD student in the Computer Systems group at the Vrije Universiteit Amsterdam. She received her MSc degree from the Universiteit van Amsterdam. Her research interests include peer-to-peer systems and ad-hoc networks. Her recent work focuses on information dissemination in ad-hoc environments.Maarten van Steen is professor of Computer Science at the Vrije Universiteit Amsterdam. His research concentrates on large-scale distributed systems, notably content delivery networks and peer-to-peer systems. He is senior member of the IEEE and member of the ACM.