In this paper, we sketch a novel gossip-based scheme that allows all the nodes in an n-node overlay network to compute a common aggregate (MAX) of their values using O(n log log n) messages within O(log n) rounds of communication. The proposed algorithm can be intuitively extended to compute other aggregates such as MIN, SUM, AVERAGE, and RANK. In contrast, the best known gossip-based algorithms for computing these aggregates require either O(n log n) messages and O(log n) rounds or O(n log log n) messages and O(log n log log n) rounds. Preliminary simulations confirm our analytical findings. Our result is achieved relaxing the hypothesis that nodes are address-oblivious, raising the interesting question whether this paradigm (address-aware) is more expressive than the address-oblivious one.
Gossip-based aggregate computation, computing faster with non address-oblivious schemes
PODC 2008, 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 18-21, 2008, Toronto, Canada
© ACM, 2008. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PODC 2008, 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 18-21, 2008, Toronto, Canada http://dx.doi.org/10.1145/1400751.1400837
PERMALINK : https://www.eurecom.fr/publication/2505