Please use this identifier to cite or link to this item:
Title: The cost of fault tolerance in multi-party communication complexity
Authors: Chen, B.
Yu, H. 
Zhao, Y.
Gibbons, P.B.
Keywords: aggregation functions
communication complexity
fault tolerance
promise problems
wireless networks
Issue Date: 2012
Citation: Chen, B.,Yu, H.,Zhao, Y.,Gibbons, P.B. (2012). The cost of fault tolerance in multi-party communication complexity. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing : 57-66. ScholarBank@NUS Repository.
Abstract: 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 crash failures. It is thus natural to ask "If we want to compute a certain function in a fault-tolerant way, what will the communication complexity be?" This natural question, interestingly, has not been formally posed and thoroughly studied prior to this work. Whether fault-tolerant communication complexity is interesting to study largely depends on how big a difference failures make. This paper proves that the impact of failures is significant, at least for the SUM aggregation function in general networks: 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 SUM. Our results also imply the optimality (within polylog factors) of some recent fault-tolerant protocols for computing SUM via duplicate-insensitive techniques, thereby answering an open question as well. Part of our results are obtained via a novel reduction from a new two-party problem UNIONSIZECP that we introduce. UNIONSIZECP comes with a novel cycle promise, which is the key enabler of our reduction. We further prove that this cycle promise and UNIONSIZECP likely play a fundamental role in reasoning about fault-tolerant communication complexity. © 2012 ACM.
Source Title: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
ISBN: 9781450314503
DOI: 10.1145/2332432.2332442
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Apr 21, 2019

Page view(s)

checked on Apr 19, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.