{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T16:04:47Z","timestamp":1774195487984,"version":"3.50.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"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. Algorithms"],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:p>A common approach for dealing with large datasets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive datasets, however, even making a single pass over the data is prohibitive. Therefore, streaming computations must be distributed over many machines. In practice, obtaining significant speedups using distributed computation has numerous challenges including synchronization, load balancing, overcoming processor failures, and data distribution. Successful systems in practice such as Google's MapReduce and Apache's Hadoop address these problems by only allowing a<jats:italic>certain class<\/jats:italic>of highly distributable tasks defined by local computations that can be applied in any order to the input.<\/jats:p><jats:p>The fundamental question that arises is: How does the class of computational tasks supported by these systems differ from the class for which streaming solutions exist?<\/jats:p><jats:p>We introduce a simple algorithmic model for massive, unordered, distributed (mud) computation, as implemented by these systems. We show that in principle, mud algorithms are equivalent in power to symmetric streaming algorithms. More precisely, we show that any symmetric (order-invariant) function that can be computed by a streaming algorithm can also be computed by a mud algorithm, with comparable space and communication complexity. Our simulation uses Savitch's theorem and therefore has superpolynomial time complexity. We extend our simulation result to some natural classes of approximate and randomized streaming algorithms. We also give negative results, using communication complexity arguments to prove that extensions to private randomness, promise problems, and indeterminate functions are impossible. We also introduce an extension of the mud model to multiple keys and multiple rounds.<\/jats:p>","DOI":"10.1145\/1824777.1824786","type":"journal-article","created":{"date-parts":[[2010,9,2]],"date-time":"2010-09-02T13:14:24Z","timestamp":1283433264000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["On distributing symmetric streaming computations"],"prefix":"10.1145","volume":"6","author":[{"given":"Jon","family":"Feldman","sequence":"first","affiliation":[{"name":"Google Inc., New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Google Inc., New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cliff","family":"Stein","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zoya","family":"Svitkina","sequence":"additional","affiliation":[{"name":"University of Alberta, Alberta, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Babai L. Gal A. Kimmel P. and Lokam S. 1996. Simultaneous messages and communication. Tech. rep. University of Chicago. Babai L. Gal A. Kimmel P. and Lokam S. 1996. Simultaneous messages and communication. Tech. rep. University of Chicago.","DOI":"10.1007\/3-540-59042-0_88"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Babai L. and Kimmel P. G. 1997. Randomized simultaneous messages: Solution of a problem of Yao in communication complexity. In Computational Complexity. 239. Babai L. and Kimmel P. G. 1997. Randomized simultaneous messages: Solution of a problem of Yao in communication complexity. In Computational Complexity. 239.","DOI":"10.1109\/CCC.1997.612319"},{"key":"e_1_2_1_4_1","volume-title":"Hadoop: A framework for running applications on large clusters built of commodity hardware","author":"Bialecki A.","year":"2005","unstructured":"Bialecki , A. , Cafarella , M. , Cutting , D. , and O'Malley , O. 2005 . Hadoop: A framework for running applications on large clusters built of commodity hardware . http:\/\/lucene.apache.org\/hadoop\/. Bialecki, A., Cafarella, M., Cutting, D., and O'Malley, O. 2005. Hadoop: A framework for running applications on large clusters built of commodity hardware. http:\/\/lucene.apache.org\/hadoop\/."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Annual European Symposium on Algorithms (ESA). 323--334","author":"Datar M.","unstructured":"Datar , M. and Muthukrishnan , S . 2002. Estimating rarity and similarity over data stream windows . In Proceedings of the Annual European Symposium on Algorithms (ESA). 323--334 . Datar, M. and Muthukrishnan, S. 2002. Estimating rarity and similarity over data stream windows. In Proceedings of the Annual European Symposium on Algorithms (ESA). 323--334."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI'04)","author":"Dean J.","unstructured":"Dean , J. and Ghemawat , S . 2004. MapReduce: Simplified data processing on large clusters . In Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI'04) . Dean, J. and Ghemawat, S. 2004. MapReduce: Simplified data processing on large clusters. In Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI'04)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/203244"},{"key":"e_1_2_1_9_1","unstructured":"Henzinger M. Raghavan P. and Rajagopalan S. 1998. Computing on data streams. Tech. note 1998-011 Digital Systems Research Center Palo Alto CA. Henzinger M. Raghavan P. and Rajagopalan S. 1998. Computing on data streams. Tech. note 1998-011 Digital Systems Research Center Palo Alto CA."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_2_1_11_1","unstructured":"McGregor A. Open problems in data streams research. http:\/\/www.cse.iitk.ac.in\/users\/sganguly\/data-stream-probs.pdf. McGregor A. Open problems in data streams research. http:\/\/www.cse.iitk.ac.in\/users\/sganguly\/data-stream-probs.pdf."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1340771.1340773"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.238004"},{"key":"e_1_2_1_16_1","first-page":"227","article-title":"Interpreting the data: Parallel analysis with sawzall. Sci","volume":"13","author":"Pike R.","year":"2005","unstructured":"Pike , R. , Dorward , S. , Griesemer , R. , and Quinlan , S. 2005 . Interpreting the data: Parallel analysis with sawzall. Sci . Program. J. 13 , 4, 227 -- 298 . Pike, R., Dorward, S., Griesemer, R., and Quinlan, S. 2005. Interpreting the data: Parallel analysis with sawzall. Sci. Program. J. 13, 4, 227--298.","journal-title":"Program. J."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264809"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80031-5"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824786","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1824777.1824786","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:53Z","timestamp":1750246793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824777.1824786"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1145\/1824777.1824786"],"URL":"https:\/\/doi.org\/10.1145\/1824777.1824786","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}