CUP: Controlled update propagation in peer-to-peer networks

A fundamental problem in peer-to-peer networks is that of locating content. Given the metadata of an object of interest, how do you locate the object within the peer-to-peer network? Most peer-to-peer networks return a set of index entries in response to a search query. These index entries point to the locations of replica nodes in the network that serve the content whose metadata satisfies the search query.; Once the location algorithm is decided upon, two basic problems emerge. First, can we improve upon the time it takes to resolve a search query? Second, after we resolve the search query to obtain a set of index entries, how do we choose from amongst them?; To address the first problem, many designers suggest caching index entries at intermediate nodes that lie on the path taken by a search query. However, little attention has been given to how to maintain these intermediate caches. To this end, we propose a new protocol, CUP, for performing Controlled Update Propagation in a peer-to-peer network. CUP asynchronously builds and maintains caches of index entries while answering search queries and confines propagation to updates whose cost is likely to be recovered by subsequent queries. We show that CUP significantly reduces query latency over caching at intermediate nodes and does so with completely recoverable update overhead.; The second part of the thesis focuses on how to choose amongst the returned index entries. This choice is important, because the demand for particular content should be balanced fairly across the set of replica nodes serving that content. Previous load balancing techniques base their decisions on periodic updates containing information about load or available capacity. We show that these techniques do not work well in the peer-to-peer context; either they do not handle peer node heterogeneity, or they suffer from significant load oscillations. We propose a new decentralized algorithm, Max-Cap, based on the maximum inherent capacities of the replicas and show that unlike previous algorithms, it is not tied to the timeliness or frequency of updates. Yet, Max-Cap can handle the heterogeneity of a peer-to-peer environment without suffering from load oscillations.