Team : NPA
Departure date : 02/28/2011
: 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.
: 02/11/2011 - 16h - Technicolor salle 3.402+3.418+3.422 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)