Energy is often the most constrained resource for battery-powered wireless devices, and most of the energy is often spent on transceiver usage (i.e., transmitting and receiving packets) rather than computation. In this article, we study the energy complexity of fundamental problems in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions. We consider four collision detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD (in which only transmitters detect collisions), Receiver-CD (in which only listeners detect collisions), and No-CD (in which no one detects collisions). The take-away message of our results is quite surprising. For randomized algorithms, there is an exponential gap between the energy complexity of Sender-CD and Receiver-CD: and for deterministic algorithms, there is another exponential gap in energy complexity, but in the reverse direction: Precisely, the randomized energy complexity of Leader Election is Θ(log * n) in Sender-CD but Θ(log(log * n)) in Receiver-CD, where n is the number of devices, which is unknown to the devices at the beginning; the deterministic complexity of Leader Election is Θ(log N ) in Receiver-CD but Θ(log log N ) in Sender-CD, where N is the size of the ID space. There is a tradeoff between time and energy. We provide a new upper bound on the time-energy tradeoff curve for randomized algorithms. A critical component of this algorithm is a new deterministic Leader Election algorithm for dense instances, when n = Θ(N ), with inverse Ackermann energy complexity. -CD. Each transmitter and listener receives one of three signals: λ S (silence, if zero devices transmit), λ N (noise, if ≥ 2 devices transmit), or a message m ∈ M (if one device transmits). Sender-CD. (Often called "No-CD" [27]) Each transmitter and listener receives one of two signals: λ S (zero or ≥ 2 devices transmit), or a message m ∈ M (if one device transmits). Observe that the Sender-CD model has no explicit collision detection but still allows for sneaky collision detection: if a sender hears λ S , it can infer that there was at least one other sender. Receiver-CD. Transmitters receive no signal. Each listener receives one of three signals: λ S (silence, if zero devices transmit), λ N (noise, if ≥ 2 devices transmit), or a message m ∈ M (if one device transmits). No-CD. Transmitters receive no signal. Listeners receive one of two signals: λ S (zero or ≥ 2 devices transmit) or a message m ∈ M. Each of the four models comes in both randomized and deterministic variants. A key issue is breaking symmetry. Whereas randomized models easily accomplish this by having devices flip independent random coins, deterministic models depend on having pre-assigned unique IDs to break symmetry. Randomized Model. In the randomized model, all n devices begin in exactly the same state and can break symmetry by generating private random bits. The number n is unknown and unbounded. The maximum allowed failure probability of a randomized algorithm is at most 1/poly(n). In a failed execution, devices may consume unbounded energy and never halt [8, 28, 29 ]. Deterministic Model. All n devices have unique IDs in the range Leader Election. Exactly one device designates itself the leader and all others designate themselves follower. For technical reasons, we require that the computation ends when the leader sends a message while every follower listens to the channel. Approximate Counting. At the end of the computation, all devices agree on an estimateñ of the network size n such thatñ = Θ(n). Census. At the end of the computation, some device announces a list of the IDs of all devices. We only study this problem in the deterministic model. Notice that any deterministic algorithm that solves Census is also capable of solving Leader Election and Approximate Counting with the same runtime and energy cost. In the randomized model, we show that the energy complexity of Leader Election and Approximate Counting are Θ(log * n) in Sender-CD and No-CD but Θ(log(log * n)) in Strong-CD and Receiver-CD. The lower bounds also apply to the contention resolution problem, and this establishes that the recent O (log(log * n)) contention resolution protocol of Bender, Kopelowitz, Pettie, and Young [7] is optimal. Our upper bounds offer a time-energy tradeoff. See Table 1 for the energy cost of our algorithm under different runtime constraints. For Leader Election, we establish matching bounds in all the deterministic models. In Strong-CD and Sender-CD, Leader Election requires Ω(log log N ) energy even when n = 2, and Census can be solved with O (log log N ) energy and O (N ) time, for any n ≤ N . However, in No-CD and Receiver-CD, the energy complexity of these problems jumps to Θ(log N ) [29] . Finally, we prove that when the input is dense in the ID space, meaning n = Θ(N ), Census can actually be computed with only O (α (N )) energy and O (N ) time, even in No-CD. To our knowledge, this is the first time inverse-Ackermann-type recursion has appeared in distributed computing. Jurdzinski et al. [27] studied the deterministic energy complexity of Leader Election in the Sender-CD model. They proved that dense instances n = Θ(N ) can be solved with O (log * N ) energy and claimed that the complexity of the sparse instances is between Ω(log log N / log log log N ) and ACM Transactions on Algorithms, Vol. 15, No. 4, Article 49. Publication date: October 2019. 49:4 Y.-J. Chang et al. O (log ϵ N ). While the lower bound is correct, the algorithm presented in Reference [27] is not. 1 The most efficient published algorithm uses O ( log N ) energy, also due to Jurdzinski et al. [30]. The same authors [28] gave a reduction from randomized Sender-CD Approximate Counting to deterministic Leader Election over ID space N = O (log n), which, using Reference [30], leads to an O ( log log n) energy algorithm for Approximate Counting. In Reference [29] , the authors gave a method for simulating Sender-CD protocols in the No-CD model and proved that deterministic No-CD Leader Election takes Ω(log N ) energy. Nakano and Olariu [40] showed that n devices in the Sender-CD model can assign themselves distinct IDs in {1, . . . , n} with O (log log n) energy in expectation. Recently, Bender et al. [7] gave a method for circuit simulation in the Strong-CD model, which led to randomized Approximate Counting and Leader Election protocols using O (log(log * n)) energy and n o (1) time. An earlier algorithm of Kardas et al. [32] solves Leader Election in the Strong-CD model in O (log ϵ n) time using O (log log log n) energy, in expectation but not with high probability. Most of the previous work in the radio network model has been concerned with time, not energy. Willard [46] proved that O (log log n) time is necessary and sufficient for one device to successfully transmit in the Strong-CD model with constant probability; see Reference [41] for tradeoffs between time and success probability. In the Sender-CD model, this problem requires Θ(log 2 n) time to solve, with probability 1 − 1/poly(n) [20, 31, 42] . Greenberg and Winograd [26] proved that if all devices need to send a message, Θ(n log n (N )) time is necessary and sufficient in the deterministic Strong-CD model. In multi-hop radio networks, Leader Election and its related problems (e.g., broadcasting and gossiping) have been studied extensively, where the bounds typically depend on both the diameter and size of the network, whether it is directed, and whether randomization and collision detection are available. See, e.g., 9, 12, 13, [15] [16] [17] 21, [35] [36] [37] . Schneider and Watterhofer [44] investigated the use of collision detection in multihop radio networks when solving archetypal problems such as MIS, (Δ + 1)-coloring, and broadcast. Their results showed that the value of collision detection depends on the problem being solved. Cornejo and Kuhn [14] introduced the beeping model, where no messages are sent; the only signals are λ N and λ S : noise and silence. The complexity of Approximate Counting was studied in Reference [8] and the "state complexity" of Leader Election was studied in Reference [25] . In adversarial settings, a jammer can interfere with communication. See References [18, 38] for leader election protocols resilient to jamming. In a resource-competitive protocol [6], the energy cost of the devices is some function of the energy cost of the jammer. See Reference [5] for resourcecompetitive contention resolution and References [24, 34] for resource-competitive point-to-point communication and broadcast protocols.
Chang et al. REF proved that for these problems, Θ(log(log * n)) and Θ(log * n) energy are optimal in CD and No-CD, respectively, for poly(n)-time algorithms.
Exponential Separations in the Energy Complexity of Leader Election
TALG
Mathematics Computer Science