PhaseA Plenary Talks

The cavity method originates from statistical mechanics, where it was invented to better understand 'disordered' physical objects such as glasses. But since the mathematical models of such 'disordered systems' are quite similar to models that had long been studied in combinatorics, it has emerged that the cavity method can be used to put forward compelling mathematical conjectures. In this talk I am going to survey the main ideas behind the cavity method, the progress that has been made towards verifying said conjectures mathematically, and also real-world applications of the ensuing mathematical work.

A multiple-access channel is a simple communication channel which is used (for example) for sharing resources - users request access by sending messages to the channel. If a single message is sent during a (discrete) time step, this message succeeds (and leaves the system). If multiple messages are sent during a time step, they collide, and must be re-sent. Users cannot communicate with each other except by sending messages to the channel. A "contention-resolution protocol" is a randomised algorithm that is used to determine how long to wait after a collision before re-sending. A famous example of a contention-resolution protocol is binary exponential backoff, in which a message that has collided k times waits for a random time, given by a geometric random variable with mean 2^k. In general, a backoff protocol is an algorithm in which a message that has collided waits for a time given by some geometric random variable with some mean, depending on k. An important property of a backoff protocol is whether it is "stable" which essentially means that the population of waiting messages stays controlled, rather than growing without bound.

We are interested in the evolution of a backoff process, where messages arrive in each step according to a Poisson distribution with some mean lambda>0, and every message runs a given backoff protocol. In the presence of queues (where messages are coordinated by queues and only the messages at the heads of queues may send) there is a phase transition - if the arrival rate lambda is too large, the process is unstable but if the arrival rate is sufficiently small, the process is stable. Not much is known about the phase transition itself.

A more fundamental question (posed by MacPhee) is whether any backoff process is stable in the absence of queues (where all messages in the system may send). Aldous proved in 1987 that binary exponential backoff is unstable for any positive arrival rate. He conjectured the same for any backoff protocol. With John Lapinskas, we have finally proved this conjecture.