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

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.

Published in:
Proceedings of the Seventh European Dependable Computing Conference, 157-166
Presented at:
Seventh European Dependable Computing Conference, Kaunas, Lithuania, May 7-9
None, None

 Record created 2008-10-13, last modified 2018-03-17

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)