Speaker: Bong-Jun Ko
Title: Replica Placement in Large Scale Distributed Networks via Asynchronous, Decentralized Graph-coloring Algorithm Sensor 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 replicas can significantly impact performance. For instance, in a multi-channel wireless network, the throughput of the system is increased by assigning channels to nodes that maximize the distance between nodes assigned to the same (i.e., replicated) channel. Content delivery networks provide another example in that object retrieval time is decreased by minimizing the distance between a requesting node and the closest replica of the content being requested.
In this talk, We present a novel decentralized, fully distributed (hierarchy-free), asynchronous algorithm that places replicas such that each node is "close" to some replica of any object. We describe our algorithm in the context of a graph with colored nodes, where a node's color indicates the replica/task that it is assigned. We show the convergence of the algorithm and some nice properties of the resulting graph coloring through analysis and simulations. Simulation results show that the algorithm generates colorings that are close to the optimal under a variety of metrics, where both proximity to the optimal coloring and running time are insensitive to the number of nodes in the graph.
Work conducted with Prof. Dan Rubenstein