Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election
Yi‐Jun Chang, Ran Duan, Shunhua Jiang · 2021
We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device ν has a unique identifier ID(ν) ∈ {1, 2, ..., N}. Energy is a scarce resource for small battery-powered devices. For such devices, most of the energy is often spent on communication, not on computation. To approximate the actual energy cost, the energy complexity of an algorithm is defined as the maximum over all devices of the number of time slots where the device transmits or listens.