Fast Distributed Algorithms for Replication in Unstructured P2P Networks

replicating data is an important issue, which is often needed for availability, reliability and per-
formance improvement. In such distributed systems, often random walks are utilized for query
routing and data replication can improve the probability of successfully ending requested items.
In this respect, we investigate the problem of ending a replica allocation to peers such that
at each peer a successful search is guaranteed while minimizing the total number of replicated
data items in network. Obviously the number of replicated data items in the whole network is
a global parameter. There exists a trade-off between the amount of local information and the
quality of the solution for the global objective function and the challenging point is to optimize
this global function only based on the local information. The literature contains huge amount of
theoretical work; Most of the proposed algorithms are, due to their complexity, far from being
practically applicable or based on some simplifying assumptions, e.g. unbounded message sizes.
In this thesis, we present a fast self-stabilizing distributed algorithm for replication based
on the LP relaxation technique, which provides a near-optimal solution and uses only small
message. The algorithm can also be applied in dynamic settings where nodes join and leave the
system. These properties are very desirable in distributed systems with unreliable components.
The most appealing features of our algorithm are its simplicity and polylogarithmic convergence.
We also provide some experimental results of the performance of the algorithm on different
network topologies such as random graphs and internet-style topologies, and introduce some
application areas of our algorithm, while proving the theoretical guarantees.