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.
Type de document :
[Research Report] RR-8044, INRIA. 2012
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

Contributeur : Hyun-Gul Roh <>
Soumis le : mardi 4 septembre 2012 - 12:59:51
Dernière modification le : jeudi 11 janvier 2018 - 06:23:13
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 09:55:29


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00724232, version 2


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



Consultations de la notice


Téléchargements de fichiers