Distributed, self-stabilizing placement of replicated resources in emerging networks

摘要

Emerging large scale distributed networking systems, such as P2P file sharing systems, sensor networks, and ad hoc wireless networks, require replication of content, functionality, or configuration to enact or optimize communication tasks. The placement of these replicated resources can significantly impact performance. We present a novel self-stabilizing, fully distributed, asynchronous, scalable protocol that can be used to place replicated resources such that each node is "close" to some copy of any object. We describe our protocol in the context of a graph with colored nodes, where a node's color indicates the replica/task that it is assigned. Our combination of theoretical results and simulation prove stabilization of the protocol, and evaluate its performance in the context of convergence time, message transmissions, and color distance. Our results show that the protocol generates colorings that are close to the optimal under a set of metrics, making such a protocol ideal for emerging networking systems.