论文标题
任意到达率的退缩协议的不稳定
Instability of backoff protocols with arbitrary arrival rates
论文作者
论文摘要
在争夺解决方案中，多个处理器试图通过有限的通信来协调通过共享渠道发送离散消息。如果两个处理器同时发送，则消息碰撞并且未成功传输。不含队列的退缩协议是一个重要的特殊情况 - 例如，Google Drive和AWS指示其用户实现二进制指数退回以处理繁忙的时期。这是一个长期以来的Aldous的猜想（IEEETrans。Inf。1987），即任何正面的处理器到达速率都不存在稳定的退缩方案。这个基本问题保持开放。只有当处理器的到达速率至少为0.42时，不稳定才知道（Goldberg等人Sicomp 2004）。我们证明，使用新的统治技术来解决主要困难，这是在紧密约束的特殊情况下，对所有退回协议的猜想，这是消息之间的强大依赖性。
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.
