On the role of mobility for multimessage gossip

Yuxin Chen, Sanjay Shakkottai, Jeffrey G. Andrews

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

We consider information dissemination in a large n-user wireless network in which k users wish to share a unique message with all other users. Each of the n users only has knowledge of its own contents and state information; this corresponds to a one-sided push-only scenario. The goal is to disseminate all messages efficiently, hopefully achieving an order-optimal spreading rate over unicast wireless random networks. First, we show that a random-push strategy-where a user sends its own or a received packet at random-is order-wise suboptimal in a random geometric graph: specifically, Ω(n) times slower than optimal spreading. It is known that this gap can be closed if each user has 'full' mobility, since this effectively creates a complete graph. We instead consider velocity-constrained mobility where at each time slot the user moves locally using a discrete random walk with velocity v(n) that is much lower than full mobility. We propose a simple two-stage dissemination strategy that alternates between individual message flooding ('self promotion') and random gossiping. We prove that this scheme achieves a close to optimal spreading rate (within only a logarithmic gap) as long as the velocity is at least v(n)=ω (log n/k). The key insight is that the mixing property introduced by the partial mobility helps users to spread in space within a relatively short period compared to the optimal spreading time, which macroscopically mimics message dissemination over a complete graph.

Original languageEnglish (US)
Article number6461940
Pages (from-to)3953-3970
Number of pages18
JournalIEEE Transactions on Information Theory
Volume59
Issue number6
DOIs
StatePublished - May 23 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'On the role of mobility for multimessage gossip'. Together they form a unique fingerprint.

  • Cite this