Gossiping with multiple messages

Sujay Sanghavi, Bruce Hajek, Laurent Massoulie

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


This paper investigates the dissemination of multiple pieces of information in large networks where users contact each other in a random uncoordinated manner, and users upload one piece per unit time. The underlying motivation is the design and analysis of piece selection protocols for peer-to-peer networks which disseminate files by dividing them into pieces. We first investigate one-sided protocols, where piece selection is based on the states of either the transmitter or the receiver. We show that any such protocol relying only on pushes, or alternatively only on pulls, will be inefficient in disseminating all pieces to all users. We propose a hybrid one-sided piece selection protocol - INTERLEAVE - and show that by using both pushes and pulls it disseminates k pieces from a single source to n users in 10(k + log n) time, while obeying the constraint that each user can upload at most one piece in one unit of time. An optimal, unrealistic centralized protocol would take k + log2 n time in this setting. Moreover, efficient dissemination is also possible if the source implements forward erasure coding, and users push the latest-released coded pieces (but do not pull). We also investigate two-sided protocols where piece selection is based on the states of both the trasmitter and the receiver. We show that it is possible to disseminate n pieces to n users in n + O (log n) time, starting from an initial state where each user has a unique piece.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2007
Subtitle of host publication26th IEEE International Conference on Computer Communications
Number of pages9
StatePublished - 2007
EventIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications - Anchorage, AK, United States
Duration: May 6 2007May 12 2007

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
Country/TerritoryUnited States
CityAnchorage, AK

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Gossiping with multiple messages'. Together they form a unique fingerprint.

Cite this