Rapid and Round-free Multi-pair Asynchronous Push-Pull Aggregation

Hyun-Gul Roh 1 Claudia Ignat 1
1 SCORE - Services and Cooperation
Inria Nancy - Grand Est, LORIA - NSS - Department of Networks, Systems and Services
Abstract : As various distributed algorithms and services demand overall information on large scale networks, the protocols that aggregate data over networks are essential, and the quality of aggregations determines the quality of those distributed algorithms and services. Though a variety of aggregation protocols have been proposed, gossip-based iterative aggregations have outstanding advantages especially in accuracy, result distribution, topology-independence, and resilience to network churns. However, most of iterative aggregations, especially push-pull style aggregations, suffer from two synchronization constraints: synchronized rounds and synchronized communication. Namely, iterative protocols generally need prior configurations to synchronize rounds over all nodes, and messages should be exchanged in a synchronous way in order to ensure accurate estimates in push-pull or push-sum protocols. This paper proposes multi-pair asynchronous push-pull aggregation (MAPPA), which liberates the push-pull aggregations from the synchronization constraints, and pursues a way to accelerate the aggregation speed. MAPPA considerably reduces aggregation times, and shows an improvement in fault-tolerance. Thanks to topology independence, inherent from gossip mechanisms, and its rapidness, MAPPA is resilient to network churns, and thus suitable for dynamic networks.
Liste complète des métadonnées

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00724232
Contributor : Hyun-Gul Roh <>
Submitted on : Tuesday, September 4, 2012 - 12:59:51 PM
Last modification on : Tuesday, December 18, 2018 - 4:26:01 PM
Document(s) archivé(s) le : Friday, December 16, 2016 - 9:55:29 AM

File

RR-8044.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00724232, version 2

Citation

Hyun-Gul Roh, Claudia Ignat. Rapid and Round-free Multi-pair Asynchronous Push-Pull Aggregation. [Research Report] RR-8044, INRIA. 2012. ⟨hal-00724232v2⟩

Share

Metrics

Record views

326

Files downloads

182