Instability of backoff protocols with arbitrary arrival rates
<p>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 impor...
| Автори: | , |
|---|---|
| Формат: | Journal article |
| Мова: | English |
| Опубліковано: |
Elsevier
2025
|
| _version_ | 1826317710495055872 |
|---|---|
| author | Goldberg, LA Lapinskas, J |
| author_facet | Goldberg, LA Lapinskas, J |
| author_sort | Goldberg, LA |
| collection | OXFORD |
| description | <p>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 (IEEE Trans. Inf. Theory 1987) 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. SICOMP 2004). 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.</p> |
| first_indexed | 2025-03-11T16:58:14Z |
| format | Journal article |
| id | oxford-uuid:7af8a2f4-0908-4b03-9a36-df9e95219ac9 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-03-11T16:58:14Z |
| publishDate | 2025 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:7af8a2f4-0908-4b03-9a36-df9e95219ac92025-02-28T13:51:55ZInstability of backoff protocols with arbitrary arrival ratesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7af8a2f4-0908-4b03-9a36-df9e95219ac9EnglishSymplectic ElementsElsevier2025Goldberg, LALapinskas, J<p>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 (IEEE Trans. Inf. Theory 1987) 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. SICOMP 2004). 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.</p> |
| spellingShingle | Goldberg, LA Lapinskas, J Instability of backoff protocols with arbitrary arrival rates |
| title | Instability of backoff protocols with arbitrary arrival rates |
| title_full | Instability of backoff protocols with arbitrary arrival rates |
| title_fullStr | Instability of backoff protocols with arbitrary arrival rates |
| title_full_unstemmed | Instability of backoff protocols with arbitrary arrival rates |
| title_short | Instability of backoff protocols with arbitrary arrival rates |
| title_sort | instability of backoff protocols with arbitrary arrival rates |
| work_keys_str_mv | AT goldbergla instabilityofbackoffprotocolswitharbitraryarrivalrates AT lapinskasj instabilityofbackoffprotocolswitharbitraryarrivalrates |