Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound)

TY - JOUR

T1 - Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound)

AU - Farach-Colton, Martín

AU - Fernández Anta, Antonio

AU - Mosteiro, Miguel A.

N1 - Funding Information: This work was supported by the National Science Foundation (CCF-0937829, CCF-1114930), Comunidad de Madrid grant S2009TIC-1692, MINECO grant TEC2011-29688-C02-01, and National Natural Science Foundation of China grant 61020106002.

PY - 2013/2/11

Y1 - 2013/2/11

N2 - Gossiping is a well-studied problem in Radio Networks. However, due to the strong resource limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we study the Gossiping problem in the restrictive context of Sensor Networks. We present a distributed algorithm that completes Gossiping with high probability in a Sensor Network of unknown topology and adversarial start-up. This algorithm exploits the geometry of sensor node distributions to achieve an optimal running time of Θ(D+Δ), where D is the diameter and Δ the maximum degree of the network. Given that any algorithm for Gossiping also solves the Broadcast problem, this result shows that the classical Broadcast lower bound of Kushilevitz and Mansour does not hold if nodes are allowed to do preprocessing. The proposed algorithm requires that a linear number of messages be stored and transmitted per unit time. We also show an optimal distributed algorithm that solves the problem in linear time for the case where only a constant number of messages can be stored.

AB - Gossiping is a well-studied problem in Radio Networks. However, due to the strong resource limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we study the Gossiping problem in the restrictive context of Sensor Networks. We present a distributed algorithm that completes Gossiping with high probability in a Sensor Network of unknown topology and adversarial start-up. This algorithm exploits the geometry of sensor node distributions to achieve an optimal running time of Θ(D+Δ), where D is the diameter and Δ the maximum degree of the network. Given that any algorithm for Gossiping also solves the Broadcast problem, this result shows that the classical Broadcast lower bound of Kushilevitz and Mansour does not hold if nodes are allowed to do preprocessing. The proposed algorithm requires that a linear number of messages be stored and transmitted per unit time. We also show an optimal distributed algorithm that solves the problem in linear time for the case where only a constant number of messages can be stored.

KW - Broadcast

KW - Convergecast

KW - Distributed algorithms

KW - Gossiping

KW - Radio Networks

KW - Sensor Networks

UR - https://www.scopus.com/pages/publications/84873179884

UR - https://www.scopus.com/pages/publications/84873179884#tab=citedBy

U2 - 10.1016/j.tcs.2012.11.030

DO - 10.1016/j.tcs.2012.11.030

M3 - Article

SN - 0304-3975

VL - 472

SP - 60

EP - 80

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -