{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T16:50:19Z","timestamp":1770915019382,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>\n            Gossip-based communication protocols are appealing in large-scale distributed applications such as information dissemination, aggregation, and overlay topology management. This paper factors out a fundamental mechanism at the heart of all these protocols: the\n            <jats:italic>peer-sampling<\/jats:italic>\n            service. In short, this service provides every node with peers to gossip with. We promote this service to the level of a first-class abstraction of a large-scale distributed system, similar to a name service being a first-class abstraction of a local-area system. We present a generic framework to implement a peer-sampling service in a decentralized manner by constructing and maintaining\n            <jats:italic>dynamic unstructured<\/jats:italic>\n            overlays through gossiping membership information itself. Our framework generalizes existing approaches and makes it easy to discover new ones. We use this framework to empirically explore and compare several implementations of the peer-sampling service. Through extensive simulation experiments we show that---although all protocols provide a good quality uniform random stream of peers to each node locally---traditional theoretical assumptions about the randomness of the unstructured overlays as a whole do not hold in any of the instances. We also show that different design decisions result in severe differences from the point of view of two crucial aspects: load balancing and fault tolerance. Our simulations are validated by means of a wide-area implementation.\n          <\/jats:p>","DOI":"10.1145\/1275517.1275520","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":359,"title":["Gossip-based peer sampling"],"prefix":"10.1145","volume":"25","author":[{"given":"M\u00e1rk","family":"Jelasity","sequence":"first","affiliation":[{"name":"University of Szeged and Hungarian Academy of Sciences, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Spyros","family":"Voulgaris","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anne-Marie","family":"Kermarrec","sequence":"additional","affiliation":[{"name":"INRIA, Rennes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"van Steen","sequence":"additional","affiliation":[{"name":"Vrije Universiteit, Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/35019019"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073871"},{"key":"e_1_2_1_3_1","volume-title":"Linked: The New Science of Networks. Perseus","author":"Barab\u00e1si A.-L.","year":"2002"},{"key":"e_1_2_1_4_1","volume-title":"Understanding Availability. In 2nd International Workshop on Peer-to-Peer Systems. Lecture Notes in Computer Science. Springer-Verlag","author":"Bhagwan R."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/312203.312207"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03)","author":"Dabek F."},{"key":"e_1_2_1_7_1","unstructured":"DAS2. The distributed ASCI supercomputer 2 (DAS-2). http:\/\/www.cs.vu.nl\/das2\/.  DAS2. The distributed ASCI supercomputer 2 (DAS-2). http:\/\/www.cs.vu.nl\/das2\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018730110112519"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/945506.945507"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2004.1297243"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1176982"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/qre.473"},{"key":"e_1_2_1_14_1","volume-title":"Middleware","author":"Jelasity M.","year":"2004"},{"key":"e_1_2_1_15_1","volume-title":"Department of Computer Science, Vrije Universiteit Amsterdam","author":"Jelasity M."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMPDP.2004.1271446"},{"key":"e_1_2_1_17_1","volume-title":"Eds. Lecture Notes in Artificial Intelligence","volume":"2977","author":"Jelasity M."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082469.1082470"},{"key":"e_1_2_1_19_1","volume-title":"Randomized Rumor Spreading. In 14th Symposium on the Foundations of Computer Science. IEEE Computer Society Press","author":"Karp R. M."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)","author":"Kempe D."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1189583"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011786"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS'03)","author":"Kosti\u0107 D."},{"key":"e_1_2_1_24_1","unstructured":"Kowalczyk W. and Vlassis N. 2005. Newscast EM. In 17th Advances in Neural Information Processing Systems (NIPS). L. K. Saul Y. Weiss and L. Bottou Eds. MIT Press Cambridge MA 713--720.  Kowalczyk W. and Vlassis N. 2005. Newscast EM. In 17th Advances in Neural Information Processing Systems (NIPS). L. K. Saul Y. Weiss and L. Bottou Eds. MIT Press Cambridge MA 713--720."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03)","author":"Law C."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Li M. and Vit\u00e1nyi P. 1997. An Introduction to Kolmogorov Complexity and its Applications 2nd Ed. Springer Verlag.   Li M. and Vit\u00e1nyi P. 1997. An Introduction to Kolmogorov Complexity and its Applications 2nd Ed. Springer Verlag.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863999"},{"key":"e_1_2_1_28_1","volume-title":"The Marsaglia random number CDROM including the Diehard battery of tests of randomness","author":"Marsaglia G."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v007.i03"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Society, 19--28","author":"Montresor A."},{"key":"e_1_2_1_31_1","volume-title":"Handbook of Graphs and Networks: From the Genome to the Internet","author":"Newman M. E. J."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.814666"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.63.066117"},{"key":"e_1_2_1_34_1","unstructured":"PeerSim. PeerSim. http:\/\/peersim.sourceforge.net\/.  PeerSim. PeerSim. http:\/\/peersim.sourceforge.net\/."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0147013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_37_1","volume-title":"Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Middleware","author":"Rowstron A.","year":"2001"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00530-003-0088-1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.826277"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.818778"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_42_1","volume-title":"International Conference on Dependable Systems and Networks. IEEE Computer Society Press","author":"Sun Q."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/762483.762485"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"van Renesse R. Minsky Y. and Hayden M. 1998. A gossip-style failure detection service. In Middleware 1998. 55--70.   van Renesse R. Minsky Y. and Hayden M. 1998. A gossip-style failure detection service. In Middleware 1998. 55--70.","DOI":"10.1007\/978-1-4471-1283-9_4"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10922-005-4441-x"},{"key":"e_1_2_1_46_1","series-title":"Lecture Notes in Computer Science","volume-title":"14th Workshop on Distributed Systems: Operations and Management","author":"Voulgaris S."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the IEEE INFOCOM.","author":"Zhong M."}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1275517.1275520","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1275517.1275520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:30Z","timestamp":1750276830000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1275517.1275520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1275517.1275520"],"URL":"https:\/\/doi.org\/10.1145\/1275517.1275520","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}