{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T00:16:58Z","timestamp":1783037818074,"version":"3.54.6"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T00:00:00Z","timestamp":1122854400000},"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":[[2005,8]]},"abstract":"<jats:p>\n            As computer networks increase in size, become more heterogeneous and span greater geographic distances, applications must be designed to cope with the very large scale, poor reliability, and often, with the extreme dynamism of the underlying network.\n            <jats:italic>Aggregation<\/jats:italic>\n            is a key functional building block for such applications: it refers to a set of functions that provide components of a distributed system access to global information including network size, average load, average uptime, location and description of hotspots, and so on. Local access to global information is often very useful, if not indispensable for building applications that are robust and adaptive. For example, in an industrial control application, some aggregate value reaching a threshold may trigger the execution of certain actions; a distributed storage system will want to know the total available free space; load-balancing protocols may benefit from knowing the target average load so as to minimize the load they transfer. We propose a gossip-based protocol for computing aggregate values over network components in a fully decentralized fashion. The class of aggregate functions we can compute is very broad and includes many useful special cases such as counting, averages, sums, products, and extremal values. The protocol is suitable for extremely large and highly dynamic systems due to its proactive structure---all nodes receive the aggregate value continuously, thus being able to track any changes in the system. The protocol is also extremely lightweight, making it suitable for many distributed applications including peer-to-peer and grid computing systems. We demonstrate the efficiency and robustness of our gossip-based protocol both theoretically and experimentally under a variety of scenarios including node and communication failures.\n          <\/jats:p>","DOI":"10.1145\/1082469.1082470","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"219-252","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":518,"title":["Gossip-based aggregation in large dynamic networks"],"prefix":"10.1145","volume":"23","author":[{"given":"M\u00e1rk","family":"Jelasity","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto","family":"Montresor","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ozalp","family":"Babaoglu","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Bologna, Bologna, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Barab\u00e1si A.-L. 2002. Linked: the new science of networks. Perseus Cambridge Mass.  Barab\u00e1si A.-L. 2002. Linked: the new science of networks. Perseus Cambridge Mass."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the First Symposium on Network Systems Design and Implementation (NSDI'04)","author":"Bavier A."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (PODC'87)","author":"Demers A.","year":"1840"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5931"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2004.1297243"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1094"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0075"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on Dependable Systems and Networks (DSN'01)","author":"Gupta I."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.08.011"},{"key":"e_1_2_1_10_1","volume-title":"Middleware","author":"Jelasity M.","year":"2004"},{"key":"e_1_2_1_11_1","unstructured":"Jelasity M. Montresor A. and Babaoglu O. 2004a. Detection and removal of malicious peers in gossip-based protocols. In FuDiCo II: S.O.S. Bertinoro Italy. http:\/\/www.cs.utexas.edu\/users\/lorenzo\/sos\/.  Jelasity M. Montresor A. and Babaoglu O. 2004a. Detection and removal of malicious peers in gossip-based protocols. In FuDiCo II: S.O.S. Bertinoro Italy. http:\/\/www.cs.utexas.edu\/users\/lorenzo\/sos\/."},{"key":"e_1_2_1_12_1","volume-title":"Eds. Lecture Notes in Artificial Intelligence","volume":"2977","author":"Jelasity M."},{"key":"e_1_2_1_14_1","unstructured":"Joseph J. and Fellenstein C. 2003. Grid Computing. Prentice Hall.   Joseph J. and Fellenstein C. 2003. Grid Computing. Prentice Hall."},{"key":"e_1_2_1_15_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_16_1","doi-asserted-by":"crossref","unstructured":"Kutylowski M.\n     and \n      \n      \n      Letkiewicz D\n      \n  \n  . \n  2003\n  . Computing average value in ad hoc networks. In Mathematical Foundations of Computer Science (MFCS'2003) B. Rovan and P. Vojt\u00e1\u0161 Eds. Number 2747 in \n  Lecture Notes in Computer Science\n  . \n  Springer 511--520.  Kutylowski M. and Letkiewicz D. 2003. Computing average value in ad hoc networks. In Mathematical Foundations of Computer Science (MFCS'2003) B. Rovan and P. Vojt\u00e1\u0161 Eds. Number 2747 in Lecture Notes in Computer Science. Springer 511--520.","DOI":"10.1007\/978-3-540-45138-9_45"},{"key":"e_1_2_1_17_1","volume-title":"Fourth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'02)","author":"Madden S."},{"key":"e_1_2_1_18_1","volume-title":"Tech. Rep. HPL-2002-57, HP Labs, Palo Alto.","author":"Milojicic D. S.","year":"2002"},{"key":"e_1_2_1_19_1","volume-title":"Tech. Rep. UBLCS-2004-18","author":"Montresor A.","year":"2004"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Nekovee M. Soppera A. and Burbridge T. 2003. An adaptive method for dynamic audience size estimation in multicast. In Group Communications and Charges: Technology and Business Models B. Stiller G. Carle M. Karsten and P. Reichl Eds. Number 2816 in Lecture Notes in Computer Science. Springer 23--33.  Nekovee M. Soppera A. and Burbridge T. 2003. An adaptive method for dynamic audience size estimation in multicast. In Group Communications and Charges: Technology and Business Models B. Stiller G. Carle M. Karsten and P. Reichl Eds. Number 2816 in Lecture Notes in Computer Science. Springer 23--33.","DOI":"10.1007\/978-3-540-39405-1_3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_22_1","unstructured":"PeerSim. http:\/\/peersim.sourceforge.net\/.  PeerSim. http:\/\/peersim.sourceforge.net\/."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/4236.978369"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00530-003-0088-1"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Future Directions in Distributed Computing","author":"van Renesse R."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/762483.762485"},{"key":"e_1_2_1_27_1","volume-title":"Middleware '98","author":"van Renesse R."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","DOI":"10.1515\/9780691188331","volume-title":"Small Worlds: The Dynamics of Networks Between Order and Randomness","author":"Watts D. J.","year":"1999"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts D. J.","year":"1998","journal-title":"Nature"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of ACM SIGCOMM","author":"Yalagandula P.","year":"2004"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082469.1082470","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1082469.1082470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:46Z","timestamp":1750263526000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082469.1082470"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1145\/1082469.1082470"],"URL":"https:\/\/doi.org\/10.1145\/1082469.1082470","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]},"assertion":[{"value":"2005-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}