An Optimal Broadcast Algorithm for Content-Addressable Networks

Ludovic Henrio 1 Fabrice Huet 1 Justine Rochas 1
1 OASIS - Active objects, semantics, Internet and security
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Structured peer-to-peer networks are powerful underlying structures for communication and storage systems in large-scale setting. In the context of the Content-Addressable Network (CAN), this paper addresses the following challenge: how to perform an efficient broadcast while the local view of the network is restricted to a set of neighbours? In existing approaches, either the broadcast is inefficient (there are dupli- cated messages) or it requires to maintain a particular structure among neighbours, e.g. a spanning tree. We define a new broadcast primitive for CAN that sends a minimum number of messages while covering the whole network, without any global knowledge. Currently, no other al- gorithm achieves those two goals in the context of CAN. In this sense, the contribution we propose in this paper is threefold. First, we pro- vide an algorithm that sends exactly one message per recipient without building a global view of the network. Second, we prove the absence of duplicated messages and the coverage of the whole network when using this algorithm. Finally, we show the practical benefits of the algorithm throughout experiments.
Type de document :
Communication dans un congrès
Baldoni, Roberto and an Steen, Maarten. OPODIS 2013 - International Conference on Principles of DIstributed Systems, Dec 2013, Nice, France. Springer, pp.176-190, 2013, 〈10.1007/978-3-319-03850-6_13〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00916301
Contributeur : Justine Rochas <>
Soumis le : mardi 10 décembre 2013 - 09:22:47
Dernière modification le : jeudi 2 janvier 2014 - 13:33:14
Document(s) archivé(s) le : vendredi 14 mars 2014 - 09:51:47

Fichier

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

Identifiants

Collections

Citation

Ludovic Henrio, Fabrice Huet, Justine Rochas. An Optimal Broadcast Algorithm for Content-Addressable Networks. Baldoni, Roberto and an Steen, Maarten. OPODIS 2013 - International Conference on Principles of DIstributed Systems, Dec 2013, Nice, France. Springer, pp.176-190, 2013, 〈10.1007/978-3-319-03850-6_13〉. 〈hal-00916301〉

Partager

Métriques

Consultations de
la notice

275

Téléchargements du document

139