Gossiping in networks: Towards understanding the power of protocols and network coding

Distributed protocols for peer-to-peer file sharing, such as BitTorrent, have been highly successful in recent years. The theory for understanding this success has lagged far behind the practice. There is also much room to understand the relative strengths of protocols and network coding - in particular how they compete with each other and how they complement each other, in the arena of peer-to-peer file sharing. In this talk I shall discuss some recent results on the theory of peer-to-peer file sharing. For example, with one-sided exchange of piece information and soft constraints on upload bandwidth, dissemination of k pieces among n users can be completed within 3.2 k + (2+o(1)) log n time steps, with high probability as n gets large. With two sided exchange of information, completion time n + O(log n) suffices, with high probability as n gets large. A common problem with file sharing protocols is how to insure that users receive each and every piece. Network coding is one approach to address that problem. The talk is largely based on the paper, Sujay Sanghavi, BH, and Laurent Massoulie, "Gossiping with multiple messages," to appear in the IEEE Transactions on Information Theory.