{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:37Z","timestamp":1750306837804,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Human Sixth Sense Programme at the Advanced Digital Sciences Center from Singapore's Agency for Science, Technology and Research"},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2011-T2-2-042"],"award-info":[{"award-number":["MOE2011-T2-2-042"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>Multi-party communication complexity involves distributed computation of a function over inputs held by multiple distributed players. A key focus of distributed computing research, since the very beginning, has been to tolerate failures. It is thus natural to ask \u201cIf we want to compute a certain function in a fault-tolerant way, what will the communication complexity be?\u201d For this question, this article will focus specifically on (i) tolerating node crash failures, and (ii) computing the function over general topologies (instead of, e.g., just cliques).<\/jats:p>\n          <jats:p>\n            One way to approach this question is to first develop results in a simpler failure-free setting, and then \u201camend\u201d the results to take into account failures' impact. Whether this approach is effective largely depends on how big a difference failures can make. This article proves that the impact of failures is significant, at least for the Sum aggregate function in general topologies: As our central contribution, we prove that there exists (at least) an exponential gap between the non-fault-tolerant and fault-tolerant communication complexity of S\n            <jats:sc>um<\/jats:sc>\n            . This gap attests that fault-tolerant communication complexity needs to be studied separately from non-fault-tolerant communication complexity, instead of being considered as an \u201camended\u201d version of the latter. Such exponential gap is not obvious: For some other functions such as the M\n            <jats:sc>ax<\/jats:sc>\n            aggregate function, the gap is only logarithmic.\n          <\/jats:p>\n          <jats:p>\n            Part of our results are obtained via a novel reduction from a new two-party problem U\n            <jats:sc>nion<\/jats:sc>\n            S\n            <jats:sc>ize<\/jats:sc>\n            CP that we introduce. U\n            <jats:sc>nion<\/jats:sc>\n            S\n            <jats:sc>ize<\/jats:sc>\n            CP comes with a novel\n            <jats:italic>cycle promise<\/jats:italic>\n            , which is the key enabler of our reduction. We further prove that this cycle promise and U\n            <jats:sc>nion<\/jats:sc>\n            S\n            <jats:sc>ize<\/jats:sc>\n            CP likely play a fundamental role in reasoning about fault-tolerant communication complexity.\n          <\/jats:p>","DOI":"10.1145\/2597633","type":"journal-article","created":{"date-parts":[[2014,5,27]],"date-time":"2014-05-27T12:56:59Z","timestamp":1401195419000},"page":"1-64","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Cost of Fault Tolerance in Multi-Party Communication Complexity"],"prefix":"10.1145","volume":"61","author":[{"given":"Binbin","family":"Chen","sequence":"first","affiliation":[{"name":"Advanced Digital Sciences Center, Republic of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haifeng","family":"Yu","sequence":"additional","affiliation":[{"name":"National University of Singapore, Republic of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuda","family":"Zhao","sequence":"additional","affiliation":[{"name":"National University of Singapore, Republic of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phillip B.","family":"Gibbons","sequence":"additional","affiliation":[{"name":"Intel Labs Pittsburgh, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,6,2]]},"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":"publisher","DOI":"10.1109\/TIT.2010.2080850"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2009.2016247"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196771"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_16"},{"volume-title":"Proceedings of the 5th Conference on Theory of Cryptography. 213--230","author":"Beerliov\u00e1-Trub\u00edniov\u00e1 Z.","key":"e_1_2_1_8_1","unstructured":"Z. Beerliov\u00e1-Trub\u00edniov\u00e1 and M. Hirt . 2008. Perfectly-secure mpc with linear communication complexity . In Proceedings of the 5th Conference on Theory of Cryptography. 213--230 . Z. Beerliov\u00e1-Trub\u00edniov\u00e1 and M. Hirt. 2008. Perfectly-secure mpc with linear communication complexity. In Proceedings of the 5th Conference on Theory of Cryptography. 213--230."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167109"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280836"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022455407000"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993659"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993644"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/646752.704756"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332442"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810504"},{"volume-title":"Proceedings of IPSN.","author":"Chen J.","key":"e_1_2_1_21_1","unstructured":"J. Chen , G. Pandurangan , and D. Xu . 2005. Robust computation of aggregates in wireless sensor networks: Distributed randomized algorithms and analysis . In Proceedings of IPSN. J. Chen, G. Pandurangan, and D. Xu. 2005. Robust computation of aggregates in wireless sensor networks: Distributed randomized algorithms and analysis. In Proceedings of IPSN."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582738"},{"volume-title":"Proceedings of ICDE.","author":"Considine J.","key":"e_1_2_1_23_1","unstructured":"J. Considine , F. Li , G. Kollios , and J. Byers . 2004. Approximate aggregation techniques for sensor databases . In Proceedings of ICDE. J. Considine, F. Li, G. Kollios, and J. Byers. 2004. Approximate aggregation techniques for sensor databases. In Proceedings of ICDE."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2034813"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28209-6_7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129780"},{"volume-title":"Proceedings of CRYPTO. 135--155","author":"Galil Z.","key":"e_1_2_1_28_1","unstructured":"Z. Galil , S. Haber , and M. Yung . 1987. Cryptographic computation: Secure fault-tolerant protocols and the public-key model . In Proceedings of CRYPTO. 135--155 . Z. Galil, S. Haber, and M. Yung. 1987. Cryptographic computation: Secure fault-tolerant protocols and the public-key model. In Proceedings of CRYPTO. 135--155."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPDP.1993.395484"},{"volume-title":"Proceedings of SODA.","author":"Gilbert S.","key":"e_1_2_1_30_1","unstructured":"S. Gilbert and D. Kowalski . 2010. Distributed agreement with optimal communication complexity . In Proceedings of SODA. S. Gilbert and D. Kowalski. 2010. Distributed agreement with optimal communication complexity. In Proceedings of SODA."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2006.1632656"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"M. Hirt U. Maurer and B. Przydatek. 2000. Efficient secure multi-party computation. In Adv. Crypt. 143--161.   M. Hirt U. Maurer and B. Przydatek. 2000. Efficient secure multi-party computation. In Adv. Crypt. 143--161.","DOI":"10.1007\/3-540-44448-3_12"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_28"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.32"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082469.1082470"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02164-0_6"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142395"},{"volume-title":"Proceedings of FOCS.","author":"Kempe D.","key":"e_1_2_1_41_1","unstructured":"D. Kempe , A. Dobra , and J. Gehrke . 2003. Gossip-based computation of aggregate information . In Proceedings of FOCS. D. Kempe, A. Dobra, and J. Gehrke. 2003. Gossip-based computation of aggregate information. In Proceedings of FOCS."},{"volume-title":"Proceedings of ICDCN.","author":"King V.","key":"e_1_2_1_42_1","unstructured":"V. King , S. Lonargan , J. Saia , and A. Trehan . 2010. Load balanced scalable Byzantine agreement through quorum building, with full information . In Proceedings of ICDCN. V. King, S. Lonargan, J. Saia, and A. Trehan. 2010. Load balanced scalable Byzantine agreement through quorum building, with full information. In Proceedings of ICDCN."},{"volume-title":"Proceedings of DISC.","author":"King V.","key":"e_1_2_1_43_1","unstructured":"V. King and J. Saia . 2009. From almost everywhere to everywhere: Byzantine agreement with \u00d5(n3\/2) bits . In Proceedings of DISC. V. King and J. Saia. 2009. From almost everywhere to everywhere: Byzantine agreement with \u00d5(n3\/2) bits. In Proceedings of DISC."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835798"},{"volume-title":"Proceedings of SODA.","author":"King V.","key":"e_1_2_1_45_1","unstructured":"V. King , J. Saia , V. Sanwalani , and E. Vee . 2006a. Scalable leader election . In Proceedings of SODA. V. King, J. Saia, V. Sanwalani, and E. Vee. 2006a. Scalable leader election. In Proceedings of SODA."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.77"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan. 1996. Communication Complexity. Cambridge University Press.   E. Kushilevitz and N. Nisan. 1996. Communication Complexity. Cambridge University Press.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060303"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/501431.501435"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146401"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1340771.1340773"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400837"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73014"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195462"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993686"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556671"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of SODA.","author":"Woodruff D.","year":"2004","unstructured":"D. Woodruff . 2004 . Optimal space lower bounds for all frequency moments . In Proceedings of SODA. D. Woodruff. 2004. Optimal space lower bounds for all frequency moments. In Proceedings of SODA."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0130-z"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2597633","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2597633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:58Z","timestamp":1750234198000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2597633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2597633"],"URL":"https:\/\/doi.org\/10.1145\/2597633","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}