{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:19Z","timestamp":1750308139497,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,1,10]],"date-time":"2006-01-10T00:00:00Z","timestamp":1136851200000},"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":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2006,1,10]]},"abstract":"<jats:p>The need for efficient computation of approximate global state lies at the heart of a wide range of problems in distributed systems. Examples include routing in the Internet, sensor fusion, search in peer-to-peer networks, coordinated intrusion detection, and Top-K queries in stream-oriented databases. Efficient algorithms that determine approximate global state could enable near-optimal local decision-making with little overhead. In this position paper, we model this problem and summarize recent work on randomized algorithms that navigate a four-way tradeo between accuracy, robustness, performance and overhead. Despite these recent successes, many open problems remain. We believe that solving these problems can radically improve the design of robust, efficient and self-managed distributed systems<\/jats:p>","DOI":"10.1145\/1111322.1111338","type":"journal-article","created":{"date-parts":[[2006,2,6]],"date-time":"2006-02-06T18:14:10Z","timestamp":1139249650000},"page":"69-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Efficient and decentralized computation of approximate global state"],"prefix":"10.1145","volume":"36","author":[{"given":"S.","family":"Keshav","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2006,1,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498447"},{"key":"e_1_2_1_2_1","unstructured":"J. Considine F. Li G. Kollios and J. Byers \"Approximate aggregation techniques for sensor databases \" Proceedings of the International Conference on Data Engineering March 2004.   J. Considine F. Li G. Kollios and J. Byers \"Approximate aggregation techniques for sensor databases \" Proceedings of the International Conference on Data Engineering March 2004."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945450"},{"key":"e_1_2_1_6_1","unstructured":"C. Gkantsidis M. Mihail and A. Saberi \"Random walks in peer-to-peer networks \" In Proceedings of IEEE INFOCOM 2004.  C. Gkantsidis M. Mihail and A. Saberi \"Random walks in peer-to-peer networks \" In Proceedings of IEEE INFOCOM 2004."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016707.1016715"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"A. Gupta and I.S. Mumick \"Materialized views: techniques implementations and applications \" MIT Press 1999.   A. Gupta and I.S. Mumick \"Materialized views: techniques implementations and applications \" MIT Press 1999.","DOI":"10.7551\/mitpress\/4472.001.0001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863998"},{"volume-title":"IEEE FOCS","year":"2003","author":"Kempe D.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652161"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30183-7_14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060303"},{"volume-title":"Analysis and Simulation of Computer and Telecommunications Systems-MASCOTS'01","year":"2001","author":"Medina A.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031525"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633039"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/762483.762485"},{"key":"e_1_2_1_18_1","unstructured":"V. Yegneswaran P. Barford and S. Jha \"Global Intrusion Detection in the DOMINO Overlay System \" In Proceedings of NDSS San Diego CA 2004.  V. Yegneswaran P. Barford and S. Jha \"Global Intrusion Detection in the DOMINO Overlay System \" In Proceedings of NDSS San Diego CA 2004."}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1111322.1111338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1111322.1111338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:39Z","timestamp":1750262919000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1111322.1111338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,10]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1,10]]}},"alternative-id":["10.1145\/1111322.1111338"],"URL":"https:\/\/doi.org\/10.1145\/1111322.1111338","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2006,1,10]]},"assertion":[{"value":"2006-01-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}