Almost-optimal gossip-based aggregate computation
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 prot...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/97889 http://hdl.handle.net/10220/10895 |
| _version_ | 1811679453003120640 |
|---|---|
| author | Chen, Jen-Yeu Pandurangan, Gopal |
| author2 | School of Materials Science & Engineering |
| author_facet | School of Materials Science & Engineering Chen, Jen-Yeu Pandurangan, Gopal |
| author_sort | Chen, Jen-Yeu |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:09:23Z |
| format | Journal Article |
| id | ntu-10356/97889 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:09:23Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/978892023-07-14T15:54:08Z Almost-optimal gossip-based aggregate computation Chen, Jen-Yeu Pandurangan, Gopal School of Materials Science & Engineering 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. Published version 2013-07-03T02:28:31Z 2019-12-06T19:47:47Z 2013-07-03T02:28:31Z 2019-12-06T19:47:47Z 2012 2012 Journal Article Chen, J.-Y., & Pandurangan, G. Almost-Optimal Gossip-Based Aggregate Computation. SIAM Journal on Computing , 41(3), 455-483. 0097-5397 https://hdl.handle.net/10356/97889 http://hdl.handle.net/10220/10895 10.1137/100793104 en SIAM journal on computing ©2012 Society for Industrial and Applied Mathematics.This paper was published in SIAM Journal on Computing and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following official DOI: [http://dx.doi.org/ 10.1137/100793104]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. application/pdf |
| spellingShingle | Chen, Jen-Yeu Pandurangan, Gopal Almost-optimal gossip-based aggregate computation |
| title | Almost-optimal gossip-based aggregate computation |
| title_full | Almost-optimal gossip-based aggregate computation |
| title_fullStr | Almost-optimal gossip-based aggregate computation |
| title_full_unstemmed | Almost-optimal gossip-based aggregate computation |
| title_short | Almost-optimal gossip-based aggregate computation |
| title_sort | almost optimal gossip based aggregate computation |
| url | https://hdl.handle.net/10356/97889 http://hdl.handle.net/10220/10895 |
| work_keys_str_mv | AT chenjenyeu almostoptimalgossipbasedaggregatecomputation AT pandurangangopal almostoptimalgossipbasedaggregatecomputation |