Correctness of gossip-based membership under message loss

ABSTRACT

Due to their simplicity and effectiveness, gossip-based membership protocols have become the method of choice for maintaining partial membership in large P2P systems. A variety of gossip-based membership protocols were proposed. Some were shown to be effective empirically, lacking analytic understanding of their properties. Others were analyzed under simplifying assumptions, such as lossless and delay-less network. It is not clear whether the analysis results hold in dynamic networks where both nodes and network links can fail.

In this paper we try to bridge this gap. We first enumerate the desirable properties of a gossip-based membership protocol, such as view uniformity, independence, and load balance. We then propose a simple Send & Forget protocol, and show that even in the presence of message loss, it achieves the desirable properties.

REFERENCES

• 1: Andre A. Allavena , John Hopcroft, On the correctness of gossip-based membership protocols, Cornell University, Ithaca, NY, 2006
• 2: André Allavena , Alan Demers , John E. Hopcroft, Correctness of a gossip based membership protocol, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073871]
• 3: Chen Avin , Michal Koucký , Zvi Lotker, How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs), Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_11]
• 4: Omar Bakr , Idit Keidar, Evaluating the running time of a communication round over the internet, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571864]
• 5: Ziv Bar-Yossef , Roy Friedman , Gabriel Kliot, RaWMS -: random walk based lightweight membership service for wireless ad hoc network, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132932]
• 6: Edward Bortnikov , Maxim Gurevich , Idit Keidar , Gabriel Kliot , Alexander Shraer, Brahms: byzantine resilient random membership sampling, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400772]
• 7: Y. Busnel, M. Bertier, and A.-M. Kermarrec. Bridging the Gap between Population and Gossip-based Protocols. Research Report RR-6720, INRIA, 2008.
• 8: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 9: T. I. Fenner and A. M. Frieze. On the connectivity of random m-orientable graphs and digraphs. Combinatorica, 2(4):347--359, 1982.
• 10: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 11: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, SCAMP: Peer-to-Peer Lightweight Membership Service for Large-Scale Group Communication, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.44-55, November 07-09, 2001
• 12: D. Gavidia, S. Voulgaris, and M. van Steen. Epidemic-style monitoring in large-scale sensor networks. Technical Report IR-CS-012, Vrije Universiteit, Netherlands, March 2005.
• 13: C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In IEEE INFOCOM, 2004.
• 14: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 15: M. Gurevich and I. Keidar. Correctness of gossip-based membership under message loss. Technical Report CCIT Report #732, Department of Electrical Engineering, Technion, 2009.
• 16: Márk Jelasity , Spyros Voulgaris , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, Gossip-based peer sampling, ACM Transactions on Computer Systems (TOCS), v.25 n.3, p.8-es, August 2007 [doi>10.1145/1275517.1275520]
• 17: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 18: Peter Mahlmann , Christian Schindelhauer, Peer-to-peer networks based on random transformations of connected regular undirected graphs, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073992]
• 19: Peter Mahlmann , Christian Schindelhauer, Distributed random digraph transformations for peer-to-peer networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148162]
• 20: Laurent Massoulié , Erwan Le Merrer , Anne-Marie Kermarrec , Ayalvadi Ganesh, Peer counting and sampling in overlay networks: random walk methods, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146402]
• 21: Roie Melamed , Idit Keidar, Araneola: A scalable reliable multicast system for dynamic environments, Journal of Parallel and Distributed Computing, v.68 n.12, p.1539-1560, December, 2008 [doi>10.1016/j.jpdc.2008.07.011]
• 22: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.289-299, Oct. 1999
• 23: S. Voulgaris, D. Gavidia, and M. van Steen. CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays. J. of Network and Systems Management, 13(2):197--217, July 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Reliability, Theory

Keywords:
gossip, membership, peer-to-peer, random sampling