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
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
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.
Type de document :
Communication dans un congrès
Seventh European Dependable Computing Conference, EDCC-7 2008, May 2008, Kaunas, Lithuania. IEEE, pp.157-166, 2008, 〈10.1109/EDCC-7.2008.17〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00329928
Contributeur : Erwan Le Merrer <>
Soumis le : lundi 13 octobre 2008 - 16:28:48
Dernière modification le : mercredi 16 mai 2018 - 11:23:20

Lien texte intégral

Identifiants

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. IEEE, pp.157-166, 2008, 〈10.1109/EDCC-7.2008.17〉. 〈inria-00329928〉

Partager

Métriques

Consultations de la notice

434