Supervision : Serge FDIDA

Co-supervision : MASSOULIÉ Laurent

Distributed Algorithms for Peer-to-Peer Networks

This thesis consists of three parts. Each part addresses an important algorithmic problem arising in modern peer-to-peer networks.
In the first part, we analyse distributed methods for characterising user taste for content. We provably extend the applicability of spectral methods for hidden structure recovery to low-rank probabilistic models of user taste. We propose a distributed method for spectral profiling in a peer-to-peer network based on message passing performed on two separate time scales. We prove almost sure convergence to the desired eigenvectors of a user similarity matrix.
In the second part, we consider the problem of Internet distance prediction and best host selection based on few measurements. We assign each node a low-dimensional vector of network coordinates and use a pseudo-distance function in the corresponding virtual space to predict Internet latencies and bottleneck bandwidths. We advocate the use of non-metric coordinates. We provide performance bounds for a simple scheme for latency prediction, under the assumption that the observed non-metric measurements are distorted versions of well-behaved quantities. We show that exact prediction of bandwidth values is possible under a widest-path routing assumption.
In the third part, we propose and analyse a distributed method for rate control meant to ensure cost-efficient constant rate streaming in peer-to-peer networks. We show that such a scheme is indeed optimal when Random Linear Coding is performed in the network. On the contrary, via a simple example, we show that the same scheme is suboptimal when simple store-and-forward is used. In this sense, we manage to emphasise a novel benefit of RLC.

2011 Publications

• 2011
  • D.‑C. Tomozei : “Diffusion efficace d’informatique dans les réseaux Pair à Pair”, thesis, phd defence 02/11/2011, supervision Fdida, Serge, co-supervision : Massoulié, Laurent (2011)