Graduate School and Research Center in Digital Sciences

Gossip-based aggregate computation, computing faster with non address-oblivious schemes

Di Pietro, Roberto; Michiardi, Pietro

PODC 2008, 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 18-21, 2008, Toronto, Canada

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.

Document Doi Bibtex

Title:Gossip-based aggregate computation, computing faster with non address-oblivious schemes
Keywords:Algorithms, Design, Theory
Type:Conference
Language:English
City:Toronto
Country:CANADA
Date:
Department:Data Science
Eurecom ref:2505
Copyright: © 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
Bibtex: @inproceedings{EURECOM+2505, doi = {http://dx.doi.org/10.1145/1400751.1400837}, year = {2008}, title = {{G}ossip-based aggregate computation, computing faster with non address-oblivious schemes}, author = {{D}i {P}ietro, {R}oberto and {M}ichiardi, {P}ietro}, booktitle = {{PODC} 2008, 27th {A}nnual {ACM} {SIGACT}-{SIGOPS} {S}ymposium on {P}rinciples of {D}istributed {C}omputing, {A}ugust 18-21, 2008, {T}oronto, {C}anada}, address = {{T}oronto, {CANADA}}, month = {08}, url = {http://www.eurecom.fr/publication/2505} }
See also: