Access Restriction

Author Chen, Binbin ♦ Yu, Haifeng ♦ Zhao, Yuda ♦ Gibbons, Phillip B
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Aggregate functions ♦ Communication complexity ♦ Fault tolerance ♦ Promise problems
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 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?” 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). One way to approach this question is to first develop results in a simpler failure-free setting, and then “amend” 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 Sum. 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 “amended” version of the latter. Such exponential gap is not obvious: For some other functions such as the Max aggregate function, the gap is only logarithmic. 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-06-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 61
Issue Number 3
Page Count 64
Starting Page 1
Ending Page 64

Open content in new tab

   Open content in new tab
Source: ACM Digital Library