Skip to Main content Skip to Navigation
Conference papers

SONDe, a Self-Organizing Object Deployment Algorithm in Large-Scale Dynamic Systems

Erwan Le Merrer 1 Anne-Marie Kermarrec 1 Vincent Gramoli 2
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
UR1 - Université de Rennes 1, Inria Saclay - Ile de France, INSA - Institut National des Sciences Appliquées, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We present the design, correctness, and analysis of SONDe, a simple fully decentralized object deployment algorithm for highly requested systems. Given an object (service or data), SONDe provides a node with a constant upper bound (h) on the number of logical hops to access an object holder (provider), thus making tunable and predictable the communication latency between a node and any provider. In addition, SONDe is able to dynamically adapt the number of providers to reflect load variations experienced in localized portions of the system. Each node individually decides to be a provider, based on the observation of its h-hops neighborhood. We show theoretically that SONDe self-stabilizes and provides an independent-dominating set of providers. Finally simulation results, conducted over different network topologies, demonstrate the efficiency of the approach and confirm the theoretical analysis.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00329928
Contributor : Erwan Le Merrer <>
Submitted on : Monday, October 13, 2008 - 4:28:48 PM
Last modification on : Tuesday, June 15, 2021 - 4:16:39 PM

Identifiers

Citation

Erwan Le Merrer, Anne-Marie Kermarrec, Vincent Gramoli. SONDe, a Self-Organizing Object Deployment Algorithm in Large-Scale Dynamic Systems. Seventh European Dependable Computing Conference, EDCC-7 2008, May 2008, Kaunas, Lithuania. pp.157-166, ⟨10.1109/EDCC-7.2008.17⟩. ⟨inria-00329928⟩

Share

Metrics

Record views

502