  In contention resolution, multiple processors are trying to coordinate to
send discrete messages through a shared channel with sharply limited
communication. If two processors inadvertently send at the same time, the
messages collide and are not transmitted successfully. An important case is
acknowledgement-based contention resolution, in which processors cannot listen
to the channel at all; all they know is whether or not their own messages have
got through. This situation arises frequently in both networking and cloud
computing. The most common acknowledgement-based protocols in practice are
backoff protocols - variants of binary exponential backoff are used in both
Ethernet and TCP/IP, and both Google Drive and AWS instruct their users to
implement it to handle busy periods.
  In queueing models, where each processor has a queue of messages, stable
backoff protocols are already known (H{\aa}stad et al., SICOMP 1996). In
queue-free models, where each processor has a single message but processors
arrive randomly, it is a long-standing conjecture of Aldous (IEEE Trans. Inf.
Theory 1987) that no stable backoff protocols exist for any positive arrival
rate of processors. Despite exciting recent results for full-sensing protocols
which assume far greater listening capabilities of the processors (see e.g.
Bender et al. STOC 2020 or Chen et al. PODC 2021), this foundational question
remains open; here instability is only known in general when the arrival rate
of processors is at least 0.42 (Goldberg et al. SICOMP 2004). We prove Aldous'
conjecture for all backoff protocols outside of a tightly-constrained special
case using a new domination technique to get around the main difficulty, which
is the strong dependencies between messages.
