On the Role of Mobility for Multimessage Gossip

DOI10.1109/TIT.2013.2247462MaRDI QIDQ2989222zbMATH OpenFDO

Authors Yuxin Chen, Sanjay Shakkottai, Jeffrey G. Andrews

Publication date 8 June 2017

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

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

Mathematics Subject Classification ID

Internet topics (68M11) Social networks; opinion dynamics (91D30) Applications of graph theory to circuits and networks (94C15)

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, $Omega(sqrtn)$ 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)=omega(sqrtlogn/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.

Cited in

(6)

• Gossiping with multiple sends and receives
• Polynomial anonymous dynamic distributed computing without a unique leader
• Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations
• Polynomial anonymous dynamic distributed computing without a unique leader
• Anonymous adversarial dynamic networks with logarithmic memory and communication
• Quiescence of self-stabilizing gossiping among mobile agents in graphs

This page was built for publication: On the Role of Mobility for Multimessage Gossip

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