SONDe, Self-Organizing Replica Placement in Large-Scale Dynamic Systems

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