Deterministic broadcasting time in radio networks of unknown topology
- 26 June 2003
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In a seminal paper, Bar-Yehuda et al. (1992) considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks, by constructing a class of graphs of diameter 3, with the property that every broadcasting algorithm requires linear time on one of these graphs. Due to a subtle error in the argument, this result is incorrect. We construct an algorithm that broadcasts in logarithmic time on all graphs from the work of Bar-Yehuda et al. Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time /spl Omega/(4/spl radic/n) on one of these graphs. In view of the randomized algorithm, running in expected time O(D log n + log/sup 2/ n) on all n-node graphs of diameter D, our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting.Keywords
This publication has 17 references indexed in Scilit:
- Centralized broadcast in multihop radio networksJournal of Algorithms, 2003
- Faster broadcasting in unknown radio networksInformation Processing Letters, 2001
- An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio NetworksSIAM Journal on Computing, 1998
- Lower bounds for the broadcast problem in mobile radio networksDistributed Computing, 1997
- The time complexity of deterministic broadcast radio networksDiscrete Applied Mathematics, 1995
- On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomizationJournal of Computer and System Sciences, 1992
- A lower bound for radio broadcastJournal of Computer and System Sciences, 1991
- The wave expansion approach to broadcasting in multihop radio networksIEEE Transactions on Communications, 1991
- A new distributed Depth-First-Search algorithmInformation Processing Letters, 1985
- Nonrandom binary superimposed codesIEEE Transactions on Information Theory, 1964