Correctness of a gossip based membership protocol

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Correctness of a gossip based membership protocol

Full text

Pdf (202 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing table of contents

Las Vegas, NV, USA

SESSION: Peer-to-peer table of contents

Pages: 292 - 301

Year of Publication: 2005

ISBN:1-59593-994-2

Authors

André Allavena	Cornell University, Ithaca, NY
Alan Demers	Cornell University, Ithaca, NY
John E. Hopcroft	Cornell University, Ithaca, NY

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 145, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1073814.1073871 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Allavena. On the Correctness of Gossip-based Membership Protocols. PhD thesis, Cornell University, 2005.
	2	K. Birman , T. Joseph, Exploiting virtual synchrony in distributed systems, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.123-138, November 08-11, 1987, Austin, Texas, United States
	3	Fan Chung. Laplacian and the cheeger inequality for directed graphs. Annals of Combinatorics, to appear.
	4	Colin Cooper , Martin Dyer , Catherine Greenhill, Sampling regular graphs and a peer-to-peer network, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	5	Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
	6	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]
	7	Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE Transactions on Computers, v.52 n.2, p.139-149, February 2003 [doi>10.1109/TC.2003.1176982]
	8	Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
	9	M. Jelasity, W. Kowalczyk, and M. van Steen. Newscast computing. Technical report, Vrije Universiteit Amsterdam, November 2003.
	10	R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
	11	David Kempe , Jon M. Kleinberg, Protocols and Impossibility Results for Gossip-Based Communication Mechanisms, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.471-480, November 16-19, 2002
	12	David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
	13	Meng-Jang Lin , Keith Marzullo, Directional Gossip: Gossip in a Wide Area Network, Proceedings of the Third European Dependable Computing Conference on Dependable Computing, p.364-379, September 15-17, 1999
	14	K. Shen. Structure management for scalable overlay service construction. In Proc. 1st USENIX/ACM Symp. on Networked Systems Design and Implementation, 2004.
	15	Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
	16	Journal of Network and Systems Management staff, Journal of Network and Systems Management, Journal of Network and Systems Management, v.13 n.1, p.139-139, March 2005 [doi>10.1007/s10922-005-4562-2]

CITED BY 17

	Neelesh Bansod , Ashish Malgi , Byung K. Choi , Jean Mayo, MuON: Epidemic based mutual anonymity in unstructured P2P networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.5, p.915-934, April, 2008
	Ziv Bar-Yossef , Roy Friedman , Gabriel Kliot, RaWMS -: random walk based lightweight membership service for wireless ad hoc network, Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy
	Gregory Chockler , Roie Melamed , Yoav Tock , Roman Vitenberg, SpiderCast: a scalable interest-aware overlay for topic-based pub/sub communication, Proceedings of the 2007 inaugural international conference on Distributed event-based systems, June 20-22, 2007, Toronto, Ontario, Canada
	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
	Lorenzo Alvisi , Jeroen Doumen , Rachid Guerraoui , Boris Koldehofe , Harry Li , Robbert van Renesse , Gilles Tredan, How robust are gossip-based communication protocols?, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	Niels Drost , Elth Ogston , Rob V. van Nieuwpoort , Henri E. Bal, ARRG: real-world gossiping, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA
	Roberto Baldoni , Roberto Beraldi , Vivien Quema , Leonardo Querzoni , Sara Tucci-Piergiovanni, TERA: topic-based event routing for peer-to-peer architectures, Proceedings of the 2007 inaugural international conference on Distributed event-based systems, June 20-22, 2007, Toronto, Ontario, Canada
	Ziv Bar-Yossef , Roy Friedman , Gabriel Kliot, RaWMS - Random Walk Based Lightweight Membership Service for Wireless Ad Hoc Networks, ACM Transactions on Computer Systems (TOCS), v.26 n.2, p.1-66, June 2008
	Ken Birman, The promise, and limitations, of gossip protocols, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	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
	Étienne Rivière , Roberto Baldoni , Harry Li , José Pereira, Compositional gossip: a conceptual architecture for designing gossip-based applications, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	Yaacov Fernandess , Antonio Fernández , Maxime Monod, A generic theoretical framework for modeling gossip-based algorithms, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	Rena Bakhshi , Francois Bonnet , Wan Fokkink , Boudewijn Haverkort, Formal analysis techniques for gossiping protocols, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	Rena Bakhshi , Lucia Cloth , Wan Fokkink , Boudewijn R. Haverkort, MeanField analysis for the evaluation of gossip protocols, ACM SIGMETRICS Performance Evaluation Review, v.36 n.3, December 2008
	Edward Bortnikov , Maxim Gurevich , Idit Keidar , Gabriel Kliot , Alexander Shraer, Brahms: Byzantine resilient random membership sampling, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.13, p.2340-2359, August, 2009
	Maxim Gurevich , Idit Keidar, Correctness of gossip-based membership under message loss, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Rena Bakhshi , Daniela Gavidia , Wan Fokkink , Maarten van Steen, An analytical model of information dissemination for a gossip-based protocol, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.13, p.2288-2303, August, 2009