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.
Defence : 02/11/2011
Jury members :
Don Towsley (UMass) [Rapporteur]
Laurent Viennot (INRIA) [Rapporteur]
Thomas Bonald (ENST)
Matthieu Latapy (UPMC, CNRS)
Marc Lelarge (INRIA, ENS)
Muriel Médard (MIT)
Serge Fdida (UPMC, CNRS)
Laurent Massoulié (Technicolor)
- D.‑C. Tomozei : “Diffusion efficace d’informatique dans les réseaux Pair à Pair”, thesis, defence 02/11/2011, supervision Fdida, Serge, co-supervision : Massoulié, Laurent (2011)