Aldous's conjecture on instability of queue-free backoff protocols

From papers

Let a queue-free multiple-access protocol have message arrival rate λ>0\lambda>0, and let a backoff protocol be a protocol in which processors back off after transmission attempts. The protocol is stable if its queue-free system remains stable under the given arrival process.

Aldous's conjecture. In the queue-free setting, no backoff protocol is stable for any positive value of λ\lambda.

This is the foundational open question for acknowledgement-based backoff protocols: whether any such protocol can be stable at all. Aldous stated it for binary exponential backoff, while the conjecture here asserts the same instability for all backoff protocols.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Leslie Ann Goldberg and John Lapinskas, “Instability of backoff protocols with arbitrary arrival rates”, arXiv:2203.17144 (2025).

Solutions 0

No solutions have been posted yet.