Skip to Main content Skip to Navigation
Reports

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

https://hal.inria.fr/inria-00117018
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, December 6, 2006 - 5:37:36 PM
Last modification on : Thursday, January 7, 2021 - 4:28:56 PM
Long-term archiving on: : Friday, September 24, 2010 - 10:47:41 AM

Files

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

Identifiers

  • HAL Id : inria-00117018, version 4

Citation

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⟩

Share

Metrics

Record views

651

Files downloads

252