A communication network is called a radio network if its nodes exchange messages in the following restricted way. First, a send operation performed by a node delivers copies of the same message to all directly reachable nodes. Secondly, a node can successfully receive an incoming message only if exactly one of its neighbors sent a message in that step. It is this semantics of how ports at nodes send and receive messages that defines the networks rather than the fact that only radio waves are used as a medium of communication; but if that is the case then just a single frequency is used. We discuss algorithmic aspects of exchanging information in such networks, concentrating on distributed randomized protocols. Specific problems and solutions depend a lot on the topology of the underlying reachability graph and how much the nodes know about it. In single-hop networks each pair of nodes can communicate directly. This kind of networks is also known as the multiple access channel. Popular broadcasting protocols used on such channels are Aloha and the exponential backoff. Multi-hop networks may have arbitrary topology and packets need to be routed hopping through a sequence of adjacent nodes. Distributed protocols run by such networks are usually robust enough not to expect the nodes to know their neighbors. These ad-hoc networks and protocols model the situation when nodes are mobile and do not rely on a fixed infrastructure.
G asieniec, Pelc and Peleg @cite_40 compared the locally and globally synchronous models of single-hop radio networks in the context of the wakeup problem, in which the time when each station joins the protocol is controlled by an adversary, and the goal of an algorithm is to perform a successful broadcast as soon as possible. If the stations have access to a global clock then wakeup can be realized in time @math with the probability at least @math , by iterating procedure Decay . If the local clocks are not synchronized, then processors may flip coins with the probability @math of heads to come up, to decide if to transmit in a step, this yields an algorithm operating in time @math with the probability at least @math . Deterministic algorithms in such setting require time @math , and deterministic schedules are known to exist achieving time @math .
@cite_40
2093347633
This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple-access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually when the processor wakes up. We consider the fundamental problem of waking up all n processors of a completely connected broadcast system. Some processors wake up spontaneously, while others have to be woken up. Only awake processors can send messages; a sleeping processor is woken up upon hearing a message. The processors hear a message in a given round if and only if exactly one processor sends a message in that round. Our goal is to wake up all processors as fast as possible in the worst case, assuming an adversary controls which processors wake up and when. We analyze the problem in both the globally synchronous and locally synchronous models with or without the assumption that n is known to the processors. We propose randomized and deterministic algorithms for the problem, as well as lower bounds in some of the cases. These bounds establish a gap between the globally synchronous and locally synchronous models.