Aldous's conjecture on instability of queue-free backoff protocols
Let a queue-free multiple-access protocol have message arrival rate , 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 .
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.
References
- Leslie Ann Goldberg and John Lapinskas, “Instability of backoff protocols with arbitrary arrival rates”, arXiv:2203.17144 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.