A few randomized protocols in peer-to-peer networks

Abstract

This thesis studies a few randomized algorithms in application-layer peer-to-peer networks. The significant gain in scalability and resilience that peer-to-peer networks provide has made them widely used and adopted in many real-world distributed systems and applications. The unique properties of peer-to-peer networks make them particularly suitable for randomized algorithms such as random walks and gossip algorithms. We study these by developing implementations based on the Docker virtual container technology. We can thus analyze their behaviour and performance in realistic settings. We further consider the problem of identifying high-risk bottleneck links in the network with the objective of improving network reliability. We propose a randomized algorithm to solve this problem and evaluate its performance by simulations.