Fully Energy-Efficient Randomized Backoff: Slow Feedback Loops Yield Fast Contention Resolution

Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet transmission can be made in any slot. A packet is successfully sent if no other packet is also transmitted during that slot. If two or more packets are sent in the same slot, then these packets collide and fail. Listening on the channel during a slot provides ternary feedback, indicating whether that slot had (0) silence, (1) a successful transmission, or (2+) noise. No other feedback or exchange of information is available to packets. Packets are (adversarially) injected into the system over time. A packet departs the system once it is successfully sent. The goal is to send all packets while optimizing throughput, which is roughly the fraction of successful slots.Most prior contention resolution algorithms with constant throughput require a short feedback loop, in the sense that a packet's sending probability in slot t + 1 is fully determined by its internal state at slot t and the channel feedback at slot t. This paper answers the question of whether these short feedback loops are necessary; that is, how often must listening and updating occur in order to achieve constant throughput? We can restate this question in terms of energy efficiency: given that both listening and sending consume significant energy, is it possible to have a contention-resolution algorithm with ternary feedback that is efficient for both operations?A shared channel can also suffer random or adversarial noise, which causes any listener to hear noise, even when no packets are actually sent. Such noise arises due to hardware/software failures or malicious interference (all modeled as "jamming"), which can have a ruinous effect on the throughput and energy efficiency. How does noise affect our goal of long feedback loops/energy efficiency?Tying these questions together, we ask: what does a contention-resolution algorithm have to sacrifice to reduce channel accesses? Must we give up on constant throughput? What about robustness to noise? Here, we show that we need not concede anything by presenting an algorithm with the following guarantees. Suppose there are N packets arriving over time and J jammed slots, where the input is determined by an adaptive adversary. With high probability in N + J, our algorithm guarantees φ(1) throughput and polylog(N + J) channel accesses (sends or listens) per packet. We also have analogous guarantees when the input stream is infinite.