text: Radio networks are a long-studied model for distributed system of devices which communicate wirelessly. When these devices are mobile or have limited capabilities, the system is often best modeled by the ad-hoc variant, in which the devices do not know the structure of the network. A large body of work has been devoted to designing algorithms for the ad-hoc model, particularly for fundamental communications tasks such as broadcasting. Most of these algorithms, however, assume that devices have some network knowledge (usually bounds on the number of nodes in the network @math , and the diameter @math ), which may not always be realistic in systems with weak devices or gradual deployment. Very little is known about what can be done when this information is not available. This is the issue we address in this work, by presenting the first broadcasting algorithms for networks in which nodes have no prior knowledge whatsoever. We demonstrate that lack of parameter knowledge can be overcome at only a small increase in running time. Specifically, we show that in networks without collision detection, broadcast can be achieved in @math time, almost reaching the @math lower bound. We also give an algorithm for directed networks with collision detection, which requires only @math time.
  @cite_3: In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model of ad hoc radio networks with unknown topology: broadcasting and wake-up. We consider an unknown radio network, in which all nodes have no prior knowledge about network topology, and know only the size of the network @math , the maximum in-degree of any node @math , and the eccentricity of the network @math . For such networks, we first give an algorithm for wake-up, based on the existence of small universal synchronizers. This algorithm runs in @math time, the fastest known in both directed and undirected networks, improving over the previous best @math -time result across all ranges of parameters, but particularly when maximum in-degree is small. Next, we introduce a new combinatorial framework of block synchronizers and prove the existence of such objects of low size. Using this framework, we design a new deterministic ...
  @cite_7: A selection problem is among the basic communication primitives in networks. In this problem at most k participating stations have to broadcast successfully their messages. This problem is especially important in packet radio networks, where simultaneous transmissions of many neighbors result in interference among delivered messages. This work focuses on a single-hop radio networks with n-stations, also called a multiple access channel, and considers both static and dynamic versions of the selection problem. We construct a family of efficient oblivious deterministic protocols based on selectors, one of them with selection time cO(klog(n k)), and the second explicit construction with selection time cO(k polylog n). The first construction matches the lower bound Ω(klog(n k)) on deterministic oblivious selection, while the second one is the first known explicit construction better than Θ(k2). In the dynamic case we introduce the model of dynamic requests, called k-streams, which generalizes the static model and the dynamic requests with at most k participants. We prove that each oblivious deterministic protocol has latency Ω(k2 log k), and on the other hand we prove the existence of the oblivious deterministic protocol with latency cO(k2log n). In view of the existence of the randomized oblivious protocol with expected latency cO(klog(n k)), this shows that randomization is substantially better than determinism for dynamic setting. Selection problem can be applied to implement other communication primitives --- we demonstrate it in the example of broadcast problem in multi-hop ad-hoc radio networks. In particular, we design an adaptive deterministic protocol broadcasting in time cO(nlog D) in every D-hop radio network of n-stations.
summary: Deterministic algorithms for broadcasting have also been studied; for undirected networks the fastest known algorithm is the @math -time algorithm of @cite_7 , while for directed networks it is the @math -time algorithm of @cite_3 .