We consider the problem of deterministic broadcasting in radio networks when the nodes have limited knowledge about the topology of the network. We show that for every deterministic broadcasting protocol there exists a network, of radius 2, for which the protocol takes at least @math (n^ 1 4 ) rounds for broadcasting in constant diameter networks. We prove the new lower @math bound for a special family of radius 2 networks. Each network of this family consists of O( n ) components which are connected to each other via only the source node. At the heart of the proof is a novel simulation argument, which essentially says that any arbitrarily complicated strategy of the source node can be simulated by the nodes of the networks, if the source node just transmits partial topological knowledge about some component instead of arbitrary complicated messages. To the best of our knowledge this type of simulation argument is novel and may be useful in further improving the lower bound or may find use in other applications. Keywords: radio networks, deterministic broadcast, lower bound, advice string, simulation, selective families, limited topological knowledge.
@cite_22: We consider broadcasting in radio networks: one node of the network knows a message that needs to be learned by all the remaining nodes. We seek distributed deterministic algorithms to perform this task. Radio networks are modeled as directed graphs. They are unknown, in the sense that nodes are not assumed to know their neighbors, nor the size of the network, they are aware only of their individual identifying numbers. If more than one message is delivered to a node in a step then the node cannot hear any of them. Nodes cannot distinguish between such collisions and the case when no messages have been delivered in a step. The fastest previously known deterministic algorithm for deterministic distributed broadcasting in unknown radio networks was presented in [6], it worked in time O(n11 6). We develop three new deterministic distributed algorithms. Algorithm A develops further the ideas of [6] and operates in time O(n1:77291) = O(n9 5), for general networks, and in time O(n1+a+H(a)+o(1)) for sparse networks with in-degrees O(na) fora < 1=2; here H is the entropy function. Algorithm B uses a new approach and works in time O(n3 2 log1 2 n) for general networks or O(n1+a+o(1)) for sparse networks. Algorithm C further improves the performance for general networks running in time O(n3 2).
@cite_7: In a seminal paper, Bar- (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- 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.
@cite_21: 
@cite_3: We establish an O(nlog2n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(n log n). The fastest previously known algorithm for this problem works in time O(n3 2). Using our broadcasting algorithm, we develop an O(n3 2log2n) algorithm for gossiping in the same network model.
@cite_17: In this paper we present new randomized and deterministic algorithms for the classical problem of broadcasting in radio networks with unknown topology. We consider directed n-node radio networks with specified eccentricity D (maximum distance from the source node to any other node). Bar- presented an algorithm that for any n-node radio network with eccentricity D completes the broadcasting in O(D log n + log2 n) time, with high probability. This result is almost optimal, since as it has been shown by Kushilevitz and Mansour and , every randomized algorithm requires Ω (D log(n D) + log2 n) expected time to complete broadcasting.Our first main result closes the gap between the lower and upper bound: we describe an optimal randomized broadcasting algorithm whose running time complexity is O(D log (n D + log2 n), with high probability. In particular, we obtain a randomized algorithm that completes broadcasting in any n-node radio network in time O(n), with high probability.The main source of our improvement is a better "selecting sequence" used by the algorithm that brings some stronger property and improves the broadcasting time. Two types of "selecting sequences" are considered: randomized and deterministic ones. The algorithm with a randomized sequence is easier (more intuitive) to analyze but both randomized and deterministic sequences give algorithms of the same asymptotic complexity.
The problem of broadcasting on directed radio networks has received much attention. The protocol given by @cite_21 requires @math rounds for completion. This upper bound was reduced to @math rounds by a breakthrough result of @cite_22 . In a further breakthrough, @cite_3 , the authors deployed the probabilistic method to bring the upper bound from @math to within logarithmic factors of the best known lower bound @math . In @cite_7 , a further improvement has been made for small diameter networks. They establish an upper bound of @math . In @cite_17 , the authors define and deploy new combinatorial structures to reduce this gap between lower and upper bounds to @math factor i.e., give a broadcasting protocol running in @math rounds.