Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions

This paper considers the problem of computing general commutative and associative aggregate functions (such as Sum) over distributed inputs held by nodes in a distributed system, while tolerating failures. Specifically, there are N nodes in the system, and the topology among them is modeled as a general undirected graph. Whenever a node sends a message, the message is received by all of its neighbors in the graph. Each node has an input, and the goal is for a special root node (e.g., the base station in wireless sensor networks or the gateway node in wireless ad hoc networks) to learn a certain commutative and associate aggregate of all these inputs. All nodes in the system except the root node may experience crash failures, with the total number of edges incidental to failed nodes being upper bounded by f. The timing model is synchronous where protocols proceed in rounds. Within such a context, we focus on the following question:

Under any given constraint on time complexity, what is the lowest communication complexity, in terms of the number of bits sent (i.e., locally broadcast) by each node, needed for computing general commutative and associate aggregate functions?

This work, for the first time, reduces the gap between the upper bound and the lower bound for the above question from polynomial to polylog. To achieve this reduction, we present significant improvements over both the existing upper bounds and the existing lower bounds on the problem.

1. For example, if a node fails or gets partitioned from the root (due to the failure of other nodes) right before the Sum protocol starts, incorporating the node’s input into the final sum would not be possible.

2. The model in [4] slightly differs from the model in this paper. But the results there can still be trivially adapted to this paper. Such trivial adaptation will be rigorously described in Sect. 11.2.

3. We have actually proved an upper bound of \(O\left( \left( \frac{f}{b}\log N+\right. \right. \left. \left. \log N\right) \cdot \min (b,f,\log N)\right) \). But for clarity, this paper uses the simpler form of \({O\left( \frac{f}{b}\log ^2 N+\log ^2 N\right) }\) in most places. The main novelty in our lower bound is the \(\frac{f}{b\log b}\) term. The \(\frac{\log N}{\log b}\) term comes, in a relatively straightforward way, from applying the results in [7] to the output domain size of \(\varOmega (N)\).

4. We do not consider probabilistic failures (e.g., where each node fails i.i.d. with certain probability), which could be of separate interest but is beyond the scope of this paper.

5. Alternatively, one could define a result to be correct iff the result equals \(\diamond _{o\in s}o\) for some s where \(s_1\subseteq s \subseteq s_2\). All our theorems and proofs hold, without any modification, under such an alternative definition.

6. Throughout this paper, a node floods a certain message by first sending the message to its neighbors, and then the other nodes simply forward that message upon first receiving it.

7. Since B may have failed early on, we may not be able to actually get x. Nevertheless, one can achieve a similar functionality by using the maximum level information from B’s descendants. See Sect. 7 for details.

8. Note that the argument here relies on the fact that the Failed Parent Detection Phase is before the Failed Child Detection Phase.

9. Note that the argument here relies on the fact that the Failed Parent Detection Phase is before the Failed Child Detection Phase.

10. The cycle promise described here is called the “alternative form” of the cycle promise in [4].

11. The result was originally stated for functions, though it trivially applies to partial functions as well.

We thank Faith Ellen, the PODC 2014 anonymous reviewers, and the Distributed Computing anonymous reviewers for many helpful comments on this paper.

Authors and Affiliations

1. School of Computing, National University of Singapore, Computing 1, 13 Computing Drive, Singapore, 117417, Republic of Singapore

   Yuda Zhao & Haifeng Yu

2. Advanced Digital Sciences Center, 1 Fusionopolis Way, #08-10 Connexis North Tower, Singapore, 138632, Republic of Singapore

   Binbin Chen

Corresponding author

Correspondence to Haifeng Yu.

A preliminary version of this work appeared in the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2014. This work is partly supported by Singapore Ministry of Education Academic Research Fund Tier 2 grant MOE2011-T2-2-042, and partly supported by the research grant for the Human Sixth Sense Programme at the Advanced Digital Sciences Center from Singapore’s Agency for Science, Technology and Research (A*STAR).

Reprints and permissions