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.