Almost-optimal gossip-based aggregate computation

Abstract

Motivated by applications to modern networking technologies, there has been interest in designing efficient gossip-based protocols for computing aggregate functions. While gossip-based protocols provide robustness due to their randomized nature, reducing the message and time complexity of these protocols is also of paramount importance in the context of resource-constrained networks such as sensor and peer-to-peer networks. We present provably time-optimal efficient gossip-based algorithms for aggregate computation with almost optimal message complexity. Given an n-node network, our algorithms guarantee that all the nodes can compute the common aggregates (such as Max, Min, Average, Sum, and Count) of their values in optimal O(log n) time and using O(n log log n) messages. Our result improves on the algorithm of Kempe, Dobra, and Gehrke [Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, 2003, pp. 482–491] that is timeoptimal but uses O(n log n) messages, as well as on the algorithm of Kashyap et al. [Proceedings of Symposium on Principles of Database Systems, 2006, pp. 308–317] that uses O(n log log n) messages but is not time-optimal (takes O(log n log log n) time). Furthermore, we show that our algorithms can be used to improve gossip-based aggregate computation in sparse communication networks, such as in peer-to-peer networks. The main technical ingredient of our algorithm is a technique called distributed random ranking (DRR) that can be useful in other applications as well. DRR gives an efficient distributed procedure to partition the network into a forest of (disjoint) trees of small size. Since the size of each tree is small, aggregates within each tree can be efficiently obtained at their respective roots. All the roots then perform a uniform gossip algorithm on their local aggregates to reach a distributed consensus on the global aggregates. Our algorithms are non-address-oblivious. In contrast, we show a lower bound of Ω(n log n) on the message complexity of any address-oblivious algorithm for computing aggregates. This shows that non-address-oblivious algorithms are needed to obtain significantly better message complexity. Our lower bound holds regardless of the number of rounds taken or the size of the messages used. Our lower bound is the first nontrivial lower bound for gossip-based aggregate computation and also gives the first formal proof that computing aggregates is strictly harder than rumor spreading in the address-oblivious model.