Instability of backoff protocols with arbitrary arrival rates

Journal article

In contention resolution, multiple processors are trying to coordinate to send discrete messages through a shared channel with limited communication. If two processors send at the same time, the messages collide and are not transmitted successfully. Queue-free backoff protocols are an important special case — for example, Google Drive and AWS instruct their users to implement binary exponential backoff to handle busy periods. It is a long-standing conjecture of Aldous (1987) [4] that no stable backoff protocols exist for any positive arrival rate of processors. This foundational question remains open; instability is only known in general when the arrival rate of processors is at least 0.42 (Goldberg et al., 2004 [13]). We prove Aldous' conjecture for all backoff protocols outside of a tightly-constrained special case using a new domination technique to get around the main difficulty, which is the strong dependencies between messages.

Authors: Goldberg, LA; Lapinskas, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Computer and System Sciences
• Volume: 152
• Article number: 103638
• Publication date: 2025-03-04
• Acceptance date: 2025-02-24
• DOI: 10.1016/j.jcss.2025.103638
• EISSN: 1090-2724
• ISSN: 0022-0000
• Language: English
• Keywords: stability; backoff protocols; Markov chains; networks; random processes; contention resolution