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

Martín Farach-Colton, Antonio Fernández Anta, Miguel A. Mosteiro

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)60-80
    Number of pages21
    JournalTheoretical Computer Science
    StatePublished - Feb 11 2013


    • Broadcast
    • Convergecast
    • Distributed algorithms
    • Gossiping
    • Radio Networks
    • Sensor Networks

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound)'. Together they form a unique fingerprint.

    Cite this