The Cost of Fault Tolerance in Multi-Party Communication Complexity
| dc.contributor.author | CHEN, Binbin | en_US |
| dc.contributor.author | YU, Haifeng | en_US |
| dc.contributor.author | ZHAO, Yuda | en_US |
| dc.contributor.author | GIBBONS, Philip B. | en_US |
| dc.date.accessioned | 2012-05-28T09:25:33Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:06Z | |
| dc.date.available | 2012-05-28T09:25:33Z | en_US |
| dc.date.available | 2017-01-23T07:00:06Z | |
| dc.date.issued | 2012-05-17 | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 657956 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/3729 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | ;TRA5/12 | en_US |
| dc.title | The Cost of Fault Tolerance in Multi-Party Communication Complexity | en_US |
| dc.type | Technical Report | en_US |