Aldous's instability conjecture for backoff protocols
Consider a multiple-access channel in discrete time with Poisson arrivals of mean birth rate . A backoff protocol is specified by a send sequence , where a message that has experienced collisions sends at each subsequent step with probability and remains silent with probability . Aldous's conjecture. No backoff process is stable for any birth rate . This conjecture generalizes Aldous's result that binary exponential backoff is unstable for every positive birth rate. The paper proves the conjecture, so the claim is solved.
References
- Leslie Ann Goldberg and John Lapinskas, “The Instability of all Backoff Protocols”, arXiv:2602.21315 (2026).
Progress summary
Never refreshed
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.