HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, December 6, 2006 - 5:37:36 PM
Last modification on : Thursday, January 20, 2022 - 4:20:36 PM
Long-term archiving on: : Friday, September 24, 2010 - 10:47:41 AM


Files produced by the author(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⟩



Record views


Files downloads