TOMOZEI Dan-Cristian

PhD graduated
Team : NPA
Departure date : 02/28/2011

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 - 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)

2011 Publications