On adaptive deterministic gossiping in ad hoc radio networks

Leszek Gasieniec, Andrzej Lingas

    Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingResearchpeer-review

    29 Citations (SciVal)


    We study deterministic algorithms for gossiping problem in ad hoc radio networks. The gossiping problem is a communication task in which each node of the network possesses a unique single message that is to be communicated to all other nodes in the network. The efficiency of a communication algorithm in radio networks is very often expressed in terms of: max-eccentricity D, max-indegree Δ, and size (number of nodes) n of underlying graph of connections. The max-eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u, v) of nodes in the network. The max-indegree Δ of a network is the maximum of indegrees of its nodes.We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc radio networks. First we show how to subsume the O(Dn)-time bound yield by the Round-Robin procedure proposing a new Õ(√Dn)-time gossiping algorithm. Our algorithm is more efficient than the known Õ(n3/2)-time gossiping algorithms [3, 6], whenever D = O(nα) and α < 1. For large values of max-eccentricity D, we give another gossiping algorithm that works in time O(DΔ3/2 log3 n) which subsumes the O(DΔ2 log3 n) upper bound presented in [4].
    Original languageEnglish
    Title of host publicationProceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
    PublisherSociety for Industrial and Applied Mathematics
    ISBN (Print)0-89871-513-X
    Publication statusPublished - 2002
    EventSymposium on Discrete Algorithms, 2002 - San Francisco, California, United States
    Duration: 2002 Jan 62002 Jan 8
    Conference number: 13


    ConferenceSymposium on Discrete Algorithms, 2002
    Abbreviated titleACM-SIAM
    Country/TerritoryUnited States
    CitySan Francisco, California

    Subject classification (UKÄ)

    • Computer Science


    Dive into the research topics of 'On adaptive deterministic gossiping in ad hoc radio networks'. Together they form a unique fingerprint.

    Cite this