Gossiping With Multiple Messages

DOI10.1109/TIT.2007.909171MaRDI QIDQ3548820zbMATH OpenFDO

Authors Sujay Sanghavi, Bruce Hajek, Laurent Massoulié

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0612118

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Communication theory (94A05) Information theory (general) (94A15)

Abstract: 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, is 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+logn)$ time, while obeying the constraint that each user can upload at most one piece in one unit of time, with high probability for large $n$. An optimal, unrealistic centralized protocol would take $k+lo{g}_{2}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 transmitter and the receiver. We show that it is possible to disseminate $n$ pieces to $n$ users in $n+O(logn)$ time, starting from an initial state where each user has a unique piece.

Recommendations

• An analytical model of information dissemination for a gossip-based protocol
• Fast gossiping by short messages
• Optimal scheduling of peer-to-peer file dissemination
• Fast Gossiping by Short Messages
• scientific article; zbMATH DE number 857072

Cited in

(18)

• Gossiping with multiple sends and receives
• Stochastic analysis of rumor spreading with multiple pull operations
• Polynomial anonymous dynamic distributed computing without a unique leader
• Almost sure exponential convergence to consensus of random gossip algorithms
• Perfect pipelining for streaming large file in peer-to-peer networks
• scientific article; zbMATH DE number 3849231 (Why is no real title available?)
• Fast Gossiping by Short Messages
• On collaborative content distribution using multi-message gossip
• Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations
• Polynomial anonymous dynamic distributed computing without a unique leader
• When Are Two Gossips the Same?
• Variants of spreading messages
• Continuous-time stochastic analysis of rumor spreading with multiple operations
• Who started this rumor? Quantifying the natural differential privacy of gossip protocols
• Anonymous adversarial dynamic networks with logarithmic memory and communication
• Optimal scheduling of peer-to-peer file dissemination
• Stepwise fair-share buffering for gossip-based peer-to-peer data dissemination
• An analytical model of information dissemination for a gossip-based protocol

This page was built for publication: Gossiping With Multiple Messages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548820)