TY - GEN

T1 - Sharing multiple messages over mobile networks

AU - Chen, Yuxin

AU - Shakkottai, Sanjay

AU - Andrews, Jeffrey G.

PY - 2011/8/2

Y1 - 2011/8/2

N2 - Information dissemination in a large network is typically achieved when each user shares its own information or resources with each other user. Consider n users randomly located over a fixed region, and k of them wish to flood their individual messages among all other users, where each user only has knowledge of its own contents and state information. The goal is to disseminate all messages using a low-overhead strategy that is one-sided and distributed while achieving an order-optimal spreading rate over a random geometric graph. In this paper, we investigate the random-push gossip-based algorithm where message selection is based on the sender's own state in a random fashion. It is first shown that random-push is inefficient in static random geometric graphs. Specifically, it is Ω(n) times slower than optimal spreading. This gap can be closed if each user is mobile, and at each time moves locally using a random walk with velocity ν(n). We propose an efficient dissemination strategy that alternates between individual message flooding and random gossiping. We show that this scheme achieves the optimal spreading rate as long as the velocity satisfies ν(n) = ω(√log n/k). The key insight is that the mixing introduced by this velocity-limited mobility approximately uniformizes the locations of all copies of each message within the optimal spreading time, which emulates a balanced geometry-free evolution over a complete graph.

AB - Information dissemination in a large network is typically achieved when each user shares its own information or resources with each other user. Consider n users randomly located over a fixed region, and k of them wish to flood their individual messages among all other users, where each user only has knowledge of its own contents and state information. The goal is to disseminate all messages using a low-overhead strategy that is one-sided and distributed while achieving an order-optimal spreading rate over a random geometric graph. In this paper, we investigate the random-push gossip-based algorithm where message selection is based on the sender's own state in a random fashion. It is first shown that random-push is inefficient in static random geometric graphs. Specifically, it is Ω(n) times slower than optimal spreading. This gap can be closed if each user is mobile, and at each time moves locally using a random walk with velocity ν(n). We propose an efficient dissemination strategy that alternates between individual message flooding and random gossiping. We show that this scheme achieves the optimal spreading rate as long as the velocity satisfies ν(n) = ω(√log n/k). The key insight is that the mixing introduced by this velocity-limited mobility approximately uniformizes the locations of all copies of each message within the optimal spreading time, which emulates a balanced geometry-free evolution over a complete graph.

UR - http://www.scopus.com/inward/record.url?scp=79960848914&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960848914&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2011.5935245

DO - 10.1109/INFCOM.2011.5935245

M3 - Conference contribution

AN - SCOPUS:79960848914

SN - 9781424499212

T3 - Proceedings - IEEE INFOCOM

SP - 658

EP - 666

BT - 2011 Proceedings IEEE INFOCOM

T2 - IEEE INFOCOM 2011

Y2 - 10 April 2011 through 15 April 2011

ER -