Workshop on Mathematical Modeling and Analysis of Computer Networks

"Epidemic Dissemination and Efficient Broadcasting
in Peer-to-Peer Systems"

Laurent Massoulie
Thomson Research

This talk focuses on the problem of relaying a live stream of information from a source to nodes of a peer-to-peer system. Several scheduling rules for neighbour and packet selection based on local information are proposed.
In a symmetric system where capacity constraints are associated with nodes, and all nodes have the same capacities, we show that the so-called ``random neighbour / latest-packet-first'' rule achieves optimal delay for rates below 1-1/e of the optimal broadcast rate.
For arbitrary node capacities, we establish that the ``most-deprived neighbour / random useful packet'' rule achieves optimal broadcast rate.
For edge-capacitated graphs, we show that ``random useful packet'' rule achieves optimal broadcast rate. A classical characterization, due to Edmonds, of the number of spanning trees that can be packed in a graph is retrieved as a corollary.
We next discuss a more general scenario where several live streams of information are to be disseminated concurrently. In this context, we show rate optimality of ``bundled random useful packet'' rule. As a byproduct we obtain an extension to multiple commodities of Edmonds' theorem on packing of spanning trees.