SONDe, Self-Organizing Replica Placement in Large-Scale Dynamic Systems

Abstract : Initially introduced in the context of file sharing systems, the peer to peer communication paradigm goes far beyond and may be applied to a wide spectrum of distributed applications. The scalability of peer to peer applications relies both on an even distribution of the load between peers and the ability to react to system dynamics. In this paper, we present the design, analysis, and evaluation of SONDe, a simple fully decentralized replica placement algorithm. Given an object (service or data), SONDe provides a peer with a constant upper bound on the number of logical hops to access a replica holder (provider), thus making tunable and predictable the communication latency between a peer and any replica (if used with logical-physical layer mapping algorithms). In addition, SONDe is able to adapt the number of replicas dynamically to reflect load variations in localized portions of the system. Each peer decides individually whether it holds a replica, based on the observation of its local neighborhood. We show theoretically that SONDe converges and provides an independent-dominating set of providers. Finally simulation results, conducted over different network topologies, demonstrate the efficiency of the approach.
Type de document :
[Research Report] RR-6052, INRIA. 2006, pp.26
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 6 décembre 2006 - 17:37:36
Dernière modification le : mercredi 28 février 2018 - 10:22:57
Document(s) archivé(s) le : vendredi 24 septembre 2010 - 10:47:41


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


  • HAL Id : inria-00117018, version 4


Vincent Gramoli, Anne-Marie Kermarrec, Erwan Le Merrer, Didier Neveux. SONDe, Self-Organizing Replica Placement in Large-Scale Dynamic Systems. [Research Report] RR-6052, INRIA. 2006, pp.26. 〈inria-00117018v4〉



Consultations de la notice


Téléchargements de fichiers