Instability of backoff protocols with arbitrary arrival rates
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915174182551552 |
|---|---|
| author | Goldberg, Leslie Ann Lapinskas, John |
| author_facet | Goldberg, Leslie Ann Lapinskas, John |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_17144 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Instability of backoff protocols with arbitrary arrival rates Goldberg, Leslie Ann Lapinskas, John Data Structures and Algorithms Discrete Mathematics Networking and Internet Architecture Probability 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. |
| title | Instability of backoff protocols with arbitrary arrival rates |
| topic | Data Structures and Algorithms Discrete Mathematics Networking and Internet Architecture Probability |
| url | https://arxiv.org/abs/2203.17144 |