Sensor network gossiping or how to break the broadcast lower bound

Martín Farach-Colton; Miguel A. Mosteiro

doi:10.1007/978-3-540-77120-3_22

Sensor network gossiping or how to break the broadcast lower bound

Martín Farach-Colton, Miguel A. Mosteiro

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Gossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce 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. By exploiting the geometry of sensor node distributions, we present reduced, optimal running time of O(D + Δ) for an algorithm that completes gossiping with high probability in a Sensor Network of unknown topology and adversarial wake-up, where D is the diameter and Δ the maximum degree of the network. Given that an algorithm for gossiping also solves the broadcast problem, our result proves that the classic lower bound of [16] can be broken if nodes are allowed to do preprocessing.

Original language	English (US)
Title of host publication	Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
Publisher	Springer Verlag
Pages	232-243
Number of pages	12
ISBN (Print)	9783540771180
DOIs	https://doi.org/10.1007/978-3-540-77120-3_22
State	Published - 2007
Event	18th International Symposium on Algorithms and Computation, ISAAC 2007 - Sendai, Japan Duration: Dec 17 2007 → Dec 19 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4835 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	18th International Symposium on Algorithms and Computation, ISAAC 2007
Country/Territory	Japan
City	Sendai
Period	12/17/07 → 12/19/07

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-77120-3_22

Cite this

Farach-Colton, M., & Mosteiro, M. A. (2007). Sensor network gossiping or how to break the broadcast lower bound. In Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings (pp. 232-243). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4835 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-77120-3_22

Sensor network gossiping or how to break the broadcast lower bound. / Farach-Colton, Martín; Mosteiro, Miguel A.
Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. Springer Verlag, 2007. p. 232-243 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4835 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Farach-Colton, M & Mosteiro, MA 2007, Sensor network gossiping or how to break the broadcast lower bound. in Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4835 LNCS, Springer Verlag, pp. 232-243, 18th International Symposium on Algorithms and Computation, ISAAC 2007, Sendai, Japan, 12/17/07. https://doi.org/10.1007/978-3-540-77120-3_22

Farach-Colton M, Mosteiro MA. Sensor network gossiping or how to break the broadcast lower bound. In Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. Springer Verlag. 2007. p. 232-243. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-77120-3_22

@inproceedings{0c3c2982bd2d4173aeb9de4f294731ea,

title = "Sensor network gossiping or how to break the broadcast lower bound",

abstract = "Gossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce 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. By exploiting the geometry of sensor node distributions, we present reduced, optimal running time of O(D + Δ) for an algorithm that completes gossiping with high probability in a Sensor Network of unknown topology and adversarial wake-up, where D is the diameter and Δ the maximum degree of the network. Given that an algorithm for gossiping also solves the broadcast problem, our result proves that the classic lower bound of [16] can be broken if nodes are allowed to do preprocessing.",

author = "Mart{\'i}n Farach-Colton and Mosteiro, {Miguel A.}",

year = "2007",

doi = "10.1007/978-3-540-77120-3_22",

language = "English (US)",

isbn = "9783540771180",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "232--243",

booktitle = "Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings",

note = "18th International Symposium on Algorithms and Computation, ISAAC 2007 ; Conference date: 17-12-2007 Through 19-12-2007",

}

TY - GEN

T1 - Sensor network gossiping or how to break the broadcast lower bound

AU - Farach-Colton, Martín

AU - Mosteiro, Miguel A.

PY - 2007

Y1 - 2007

N2 - Gossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce 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. By exploiting the geometry of sensor node distributions, we present reduced, optimal running time of O(D + Δ) for an algorithm that completes gossiping with high probability in a Sensor Network of unknown topology and adversarial wake-up, where D is the diameter and Δ the maximum degree of the network. Given that an algorithm for gossiping also solves the broadcast problem, our result proves that the classic lower bound of [16] can be broken if nodes are allowed to do preprocessing.

AB - Gossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce 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. By exploiting the geometry of sensor node distributions, we present reduced, optimal running time of O(D + Δ) for an algorithm that completes gossiping with high probability in a Sensor Network of unknown topology and adversarial wake-up, where D is the diameter and Δ the maximum degree of the network. Given that an algorithm for gossiping also solves the broadcast problem, our result proves that the classic lower bound of [16] can be broken if nodes are allowed to do preprocessing.

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

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

U2 - 10.1007/978-3-540-77120-3_22

DO - 10.1007/978-3-540-77120-3_22

M3 - Conference contribution

AN - SCOPUS:38149116968

SN - 9783540771180

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 232

EP - 243

BT - Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings

PB - Springer Verlag

T2 - 18th International Symposium on Algorithms and Computation, ISAAC 2007

Y2 - 17 December 2007 through 19 December 2007

ER -

Sensor network gossiping or how to break the broadcast lower bound

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this