{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T11:13:06Z","timestamp":1772104386985,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007523","name":"Advanced Cyberinfrastructure","doi-asserted-by":"publisher","award":["ANI-0092678"],"award-info":[{"award-number":["ANI-0092678"]}],"id":[{"id":"10.13039\/100007523","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            Previous approaches for computing duplicate-sensitive aggregates in wireless sensor networks have used a tree topology, in order to conserve energy and to avoid double-counting sensor readings. However, a tree topology is not robust against node and communication failures, which are common in sensor networks. In this article, we present\n            <jats:italic>synopsis diffusion<\/jats:italic>\n            , a general framework for achieving significantly more accurate and reliable answers by combining energy-efficient multipath routing schemes with techniques that avoid double-counting. Synopsis diffusion avoids double-counting through the use of\n            <jats:italic>order- and duplicate-insensitive (ODI) synopses<\/jats:italic>\n            that compactly summarize intermediate results during in-network aggregation. We provide a surprisingly simple test that makes it easy to check the correctness of an ODI synopsis. We show that the properties of ODI synopses and synopsis diffusion create\n            <jats:italic>implicit<\/jats:italic>\n            acknowledgments of packet delivery. Such acknowledgments enable energy-efficient adaptation of message routes to dynamic message loss conditions, even in the presence of asymmetric links. Finally, we illustrate using extensive simulations the significant robustness, accuracy, and energy-efficiency improvements of synopsis diffusion over previous approaches.\n          <\/jats:p>","DOI":"10.1145\/1340771.1340773","type":"journal-article","created":{"date-parts":[[2008,4,8]],"date-time":"2008-04-08T15:40:00Z","timestamp":1207669200000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":82,"title":["Synopsis diffusion for robust aggregation in sensor networks"],"prefix":"10.1145","volume":"4","author":[{"given":"Suman","family":"Nath","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA"}]},{"given":"Phillip B.","family":"Gibbons","sequence":"additional","affiliation":[{"name":"Intel Research Pittsburgh, Pittsburgh, PA"}]},{"given":"Srinivasan","family":"Seshan","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Zachary","family":"Anderson","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA"}]}],"member":"320","published-online":{"date-parts":[[2008,4,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","unstructured":"Atmel AVR Microcontroller Datasheet. 2004. Go online to http:\/\/www.atmel.com\/dyn\/resources\/prod_documents\/2467s.pdf.  Atmel AVR Microcontroller Datasheet. 2004. Go online to http:\/\/www.atmel.com\/dyn\/resources\/prod_documents\/2467s.pdf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380810"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007627"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Bonnet P. Gehrke J. E. and Seshadri P. 2001. Towards sensor database systems. In IEEE Mobile Data Management. Springer Berlin Germany.   Bonnet P. Gehrke J. E. and Seshadri P. 2001. Towards sensor database systems. In IEEE Mobile Data Management. Springer Berlin Germany.","DOI":"10.1007\/3-540-44498-X_1"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of IEEE INFOCOM. IEEE Computer Society Press","author":"Boyd S.","unstructured":"Boyd , S. , Ghosh , A. , Prabhakar , B. , and Shah , D . 2005. Gossip algorithms: Design, analysis, and applications . In Proceedings of IEEE INFOCOM. IEEE Computer Society Press , Los Alamitos, CA. Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. 2005. Gossip algorithms: Design, analysis, and applications. In Proceedings of IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN).","author":"Chen J.-Y.","unstructured":"Chen , J.-Y. and Pandurangan , D. X. G. 2005. Robust aggregates computation in wireless sensor networks: Distributed randomized algorithms and analysis . In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN). Chen, J.-Y. and Pandurangan, D. X. G. 2005. Robust aggregates computation in wireless sensor networks: Distributed randomized algorithms and analysis. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 20th International Conference on Data Engineering (ICDE). IEEE Computer Society Press","author":"Considine J.","unstructured":"Considine , J. , Li , F. , Kollios , G. , and Byers , J . 2004. Approximate aggregation techniques for sensor databases . In Proceedings of the 20th International Conference on Data Engineering (ICDE). IEEE Computer Society Press , Los Alamitos, CA, 449. Considine, J., Li, F., Kollios, G., and Byers, J. 2004. Approximate aggregation techniques for sensor databases. In Proceedings of the 20th International Conference on Data Engineering (ICDE). IEEE Computer Society Press, Los Alamitos, CA, 449."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066161"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Davey B. A. and Priestley H. A. 2002. Introduction to Lattices and Order. Cambridge University Press Cambridge U.K.  Davey B. A. and Priestley H. A. 2002. Introduction to Lattices and Order. Cambridge University Press Cambridge U.K.","DOI":"10.1017\/CBO9780511809088"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Deshpande A.","unstructured":"Deshpande , A. , Guestrin , C. , Madden , S. , Hellerstein , J. M. , and Hong , W . 2004. Model-driven data acquisition in sensor networks . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA. Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J. M., and Hong, W. 2004. Model-driven data acquisition in sensor networks. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127791"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/509506.509514"},{"key":"e_1_2_1_17_1","volume-title":"Data Stream Management: Processing High-Speed Data Streams","author":"Gibbons P. B.","unstructured":"Gibbons , P. B. 2007. Distinct-values estimation over data streams . In Data Stream Management: Processing High-Speed Data Streams , M. Garofalakis, J. Gehrke, and R. Rastogi, Eds. Springer , New York, NY . Gibbons, P. B. 2007. Distinct-values estimation over data streams. In Data Stream Management: Processing High-Speed Data Streams, M. Garofalakis, J. Gehrke, and R. Rastogi, Eds. Springer, New York, NY."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Gibbons P. B. and Matias Y. 1999. Synopsis data structures for massive data sets. In External Memory Algorithms. American Mathematical Society Boston MA 39--70.   Gibbons P. B. and Matias Y. 1999. Synopsis data structures for massive data sets. In External Memory Algorithms. American Mathematical Society Boston MA 39--70.","DOI":"10.1090\/dimacs\/050\/02"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/564870.564880"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2001 International Conference on Dependable Systems and Networks (DSN). IEEE Computer Society Press","author":"Gupta I.","unstructured":"Gupta , I. , van Renesse , R. , and Birman , K. P . 2001. Scalable fault-tolerant aggregation in large process groups . In Proceedings of the 2001 International Conference on Dependable Systems and Networks (DSN). IEEE Computer Society Press , Los Alamitos, CA, 433--442. Gupta, I., van Renesse, R., and Birman, K. P. 2001. Scalable fault-tolerant aggregation in large process groups. In Proceedings of the 2001 International Conference on Dependable Systems and Networks (DSN). IEEE Computer Society Press, Los Alamitos, CA, 433--442."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345920"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 21st International Conference on Distributed Computing Systems. IEEE Computer Society Press","author":"Jenkins K.","unstructured":"Jenkins , K. , Hopkinson , K. , and Birman , K . 2001. A gossip protocol for subgroup multicast . In Proceedings of the 21st International Conference on Distributed Computing Systems. IEEE Computer Society Press , Los Alamitos, CA. Jenkins, K., Hopkinson, K., and Birman, K. 2001. A gossip protocol for subgroup multicast. In Proceedings of the 21st International Conference on Distributed Computing Systems. IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_24_1","unstructured":"Johnson D. B. and Maltz D. A. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing T. Imielinski and H. F. Korth Eds. Vol. 353. Kluwer Academic Publishers Norwell MA.  Johnson D. B. and Maltz D. A. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing T. Imielinski and H. F. Korth Eds. Vol. 353. Kluwer Academic Publishers Norwell MA."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Karp R.","unstructured":"Karp , R. , Schindelhauer , C. , Shenker , S. , and Vocking , B . 2000. Randomized rumor spreading . In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA, 565. Karp, R., Schindelhauer, C., Shenker, S., and Vocking, B. 2000. Randomized rumor spreading. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 565."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Kempe D.","unstructured":"Kempe , D. , Dobra , A. , and Gehrke , J . 2003. Gossip-based computation of aggregate information . In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA. Kempe, D., Dobra, A., and Gehrke, J. 2003. Gossip-based computation of aggregate information. In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS). USENIX","author":"Kostic D.","unstructured":"Kostic , D. , Rodriguez , A. , Albrecht , J. R. , Bhirud , A. , and Vahdat , A . 2003. Using random subsets to build scalable network services . In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS). USENIX , Berkeley, CA. Kostic, D., Rodriguez, A., Albrecht, J. R., Bhirud, A., and Vahdat, A. 2003. Using random subsets to build scalable network services. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS). USENIX, Berkeley, CA."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958506"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI). ACM Press","author":"Madden S.","unstructured":"Madden , S. , Franklin , M. J. , Hellerstein , J. M. , and Hong , W . 2002a. TAG: A tiny aggregation service for ad-hoc sensor networks . In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI). ACM Press , New York, NY, 131--146. Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2002a. TAG: A tiny aggregation service for ad-hoc sensor networks. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI). ACM Press, New York, NY, 131--146."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872817"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA). IEEE Computer Society Press","author":"Madden S.","unstructured":"Madden , S. , Szewczyk , R. , Franklin , M. J. , and Culler , D . 2002b. Supporting aggregate queries over ad-hoc wireless sensor networks . In Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA). IEEE Computer Society Press , Los Alamitos, CA, 49. Madden, S., Szewczyk, R., Franklin, M. J., and Culler, D. 2002b. Supporting aggregate queries over ad-hoc wireless sensor networks. In Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA). IEEE Computer Society Press, Los Alamitos, CA, 49."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066191"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON). IEEE Computer Society Press","author":"Mukhopadhyay S.","unstructured":"Mukhopadhyay , S. , Panigrahi , D. , and Dey , S . 2004. Model based error correction for wireless sensor networks . In Proceedings of the First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON). IEEE Computer Society Press , Los Alamitos, CA. Mukhopadhyay, S., Panigrahi, D., and Dey, S. 2004. Model based error correction for wireless sensor networks. In Proceedings of the First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON). IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_34_1","volume-title":"Data streams: Algorithms and applications. Tech. rep","author":"Muthukrishnan S.","unstructured":"Muthukrishnan , S. 2003. Data streams: Algorithms and applications. Tech. rep . Rutgers University, Piscataway , NJ. Muthukrishnan, S. 2003. Data streams: Algorithms and applications. Tech. rep. Rutgers University, Piscataway, NJ."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775059"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1098918.1098928"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958521"},{"key":"e_1_2_1_39_1","volume-title":"RMST: Reliable data transport in sensor networks. In Proceedings of 1st IEEE International Workshop on Sensor Net Protocols and Applications (SNPA)","author":"Stann F.","year":"2003","unstructured":"Stann , F. and Heidemann , J . 2003 . RMST: Reliable data transport in sensor networks. In Proceedings of 1st IEEE International Workshop on Sensor Net Protocols and Applications (SNPA) . IEEE Computer Society Press , Los Alamitos, CA . Stann, F. and Heidemann, J. 2003. RMST: Reliable data transport in sensor networks. In Proceedings of 1st IEEE International Workshop on Sensor Net Protocols and Applications (SNPA). IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 20th International Conference on Data Engineering (ICDE). IEEE Computer Society Press","author":"Tao Y.","unstructured":"Tao , Y. , Kollios , G. , Considine , J. , Li , F. , and Papadias , D . 2004. Spatio-temporal aggregation using sketches . In Proceedings of the 20th International Conference on Data Engineering (ICDE). IEEE Computer Society Press , Los Alamitos, CA, 214. Tao, Y., Kollios, G., Considine, J., Li, F., and Papadias, D. 2004. Spatio-temporal aggregation using sketches. In Proceedings of the 20th International Conference on Data Engineering (ICDE). IEEE Computer Society Press, Los Alamitos, CA, 214."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/774763.774784"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Wan C.-Y. Campbell A. T. and Krishnamurthy L. 2004. Reliable transport for sensor networks. In Wireless Sensor Networks. Springer New York NY 153--182.   Wan C.-Y. Campbell A. T. and Krishnamurthy L. 2004. Reliable transport for sensor networks. In Wireless Sensor Networks. Springer New York NY 153--182.","DOI":"10.1007\/978-1-4020-7884-2_8"},{"key":"e_1_2_1_43_1","volume-title":"Mathematics of Computation","author":"Watson E. J.","unstructured":"Watson , E. J. 1962. Mathematics of Computation . Vol. 16 . American Mathematical Society , Providence, RI , 368--369. Watson, E. J. 1962. Mathematics of Computation. Vol. 16. American Mathematical Society, Providence, RI, 368--369."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the First Conference on Innovative Data Systems Research (CIDR). Morgan Kaufmann","author":"Yao Y.","unstructured":"Yao , Y. and Gehrke , J . 2003. Query processing in sensor networks . In Proceedings of the First Conference on Innovative Data Systems Research (CIDR). Morgan Kaufmann , San Francisco, CA. Yao, Y. and Gehrke, J. 2003. Query processing in sensor networks. In Proceedings of the First Conference on Innovative Data Systems Research (CIDR). Morgan Kaufmann, San Francisco, CA."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066192"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958493"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of 1st IEEE International Workshop on Sensor Network Protocols and Applications. IEEE Computer Society Press","author":"Zhao J.","unstructured":"Zhao , J. , Govindan , R. , and Estrin , D . 2003. Computing aggregates for monitoring wireless sensor networks . In Proceedings of 1st IEEE International Workshop on Sensor Network Protocols and Applications. IEEE Computer Society Press , Los Alamitos, CA. Zhao, J., Govindan, R., and Estrin, D. 2003. Computing aggregates for monitoring wireless sensor networks. In Proceedings of 1st IEEE International Workshop on Sensor Network Protocols and Applications. IEEE Computer Society Press, Los Alamitos, CA."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1340771.1340773","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1340771.1340773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:39:13Z","timestamp":1750253953000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1340771.1340773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1340771.1340773"],"URL":"https:\/\/doi.org\/10.1145\/1340771.1340773","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"value":"1550-4859","type":"print"},{"value":"1550-4867","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2006-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}