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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2008 4th Workshop on Network Coding, Theory, and Applications, NetCod 2008
DOIs
StatePublished - Aug 25 2008
Event2008 4th Workshop on Network Coding, Theory, and Applications, NetCod 2008 - Hong Kong, Hong Kong
Duration: Jan 3 2008Jan 4 2008

Publication series

NameProceedings - 2008 4th Workshop on Network Coding, Theory, and Applications, NetCod 2008

Other

Other2008 4th Workshop on Network Coding, Theory, and Applications, NetCod 2008
Country/TerritoryHong Kong
CityHong Kong
Period1/3/081/4/08

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Gossiping in networks: Towards understanding the power of protocols and network coding'. Together they form a unique fingerprint.

Cite this