| 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. In this thesis, we present self-organizing, fully distributed, asynchronous, scalable algorithms and protocols that can be used to place replicated resources in desirable locations in three different environments.;We first explore theoretical properties of replica placement problems at a fundamental level, and develop a fully distributed protocol in the context of a graph with colored nodes, where a node's color indicates the replica/task that it is assigned. In this theoretical work, we introduce a novel mechanism with which each node in the network decides its own color, resulting in a graph coloring such that each node is close to any arbitrary replicated color. The combination of theoretical results and simulation show that the protocol stabilizes quickly to a coloring that is close to the optimal under a set of optimization criteria.;We then study the distributed server placement problem in large-scale client-server networks, such as content distribution networks (CDN) and online gaming networks, as a real-world application of our replica placement algorithm. The problem is explored in the context of a server coloring problem, where each server node is assigned a color that represents a particular server resource. Simulation results show that the distributed algorithm quickly generates a placement for multiple colors simultaneously, and reduces the expected client-server distance by almost half compared to the distance when the assignment of replicated servers is done at random.;Last, we design, implement, and evaluate a distributed channel assignment algorithm in multi-hop 802.11 mesh networks, taking a further step toward validating the effectiveness of our replica placement mechanism. While we take the same strategy in addressing the distributed assignment problem in a self-organizing manner, we also make a significant number of new contributions that deal with the unique challenges present in the wireless networking environment, from algorithmic modifications to resolving implementation-specific issues. Experimental results obtained from the testbed show that our channel assignment algorithm improves the network's capacity by 50% in comparison to a homogeneous channel assignment and by 20% in comparison to a random assignment. |
