A contention-resolution protocol is a randomised algorithm for sharing a communication channel. The most famous example is binary exponential backoff – which underlies the Ethernet. These algorithms are also used in other contexts, for example, for sharing cloud resources.

The basic communication mechanism is a multiple-access channel, where users communicate by sending messages to the channel. If a single message sends during a time step, it is successful (so it leaves the system). However, if multiple messages send during a time step, they collide, and must be re-transmitted later.

In this context, a contention-resolution protocol is a randomised algorithm that each user runs to decide whether to send a message during a given time step, or to wait. The most important question about a contention-resolution protocol is whether it is stable — essentially, whether the population of waiting messages stays controlled, or whether it grows without bound.

There has been lots of work on stability of contention-resolution protocols, which I will tell you about. My biggest focus will be on foundational questions about backoff protocols, where messages wait for random geometric intervals before re-sending.

Backoff protocols are known to be stable for positive arrival rates in models with queues, but it is still unknown how high the arrival rate can be in order to enable stability. An even more fundamental question (posed by MacPhee) is whether there is any backoff protocol that is stable for
any positive arrival rate in the model without queues (this model is more appropriate for shared-channel applications on the internet, where users come and go).

In this model, a backoff protocol is given by a sequence p = p_0,p_1,p_2 … of reals in (0,1] and an arrival rate lambda in (0,1). On a given step, the number of messages that arrive is a Poisson random variable with mean lambda. Any message that has already collided k times sends with probability p_k. If exactly one message sends, it escapes. Otherwise, all sending messages collide. Aldous showed in 1987 that binary exponential backoff (with p_k = 2^{-k}) is unstable for any positive lambda, in the sense that the resulting process is not positive recurrent (so messages build up over time). He conjectured the same for all backoff protocols.

I will tell you about progress on this conjecture, which John Lapinskas and I have finally proved.