Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel-Access Attempts, and Robustness
Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel-Access Attempts, and Robustness
复制标题
缩放指数退避：恒定吞吐量、多对数通道访问尝试和鲁棒性
DOI：
10.1145/3276769
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
Young, Maxwell
中科院分区：
文献类型：
--
作者：
Bender, Michael A.;Fineman, Jeremy T.;Gilbert, Seth;Young, Maxwell
随机指数退避是一种广泛部署的技术，用于协调对共享资源的访问。可以说，一个好的退避协议应该满足三个自然属性：（1）它应该提供恒定的吞吐量，浪费尽可能少的时间;（2）它应该要求很少的失败访问尝试，最大限度地减少浪费的工作量;（3）它应该是健壮的，即使一些访问尝试由于虚假原因失败，也能继续有效地工作。不幸的是，指数退避在其中两个方面有一些众所周知的局限性：在突发流量下，它可能会遭受次恒定的吞吐量，并且它对对抗性中断不鲁棒。本文的目标是通过使其可扩展来“修复”指数退避，特别关注进程以在线的最坏情况方式到达的情况。我们提出了一个相对简单的回退协议Re-Backoff，其核心是指数回退版本。它保证了预期的恒定吞吐量与动态进程的到来，并只需要一个预期的多对数访问尝试每个process.Re-Backoffis也鲁棒的时期，共享资源是不可用的一段时间。如果对于D时隙不可用，则重新退避提供以下保证。对于n个数据包，成功发送一个数据包的预期访问尝试次数为O（log 2（n+D））。对于无限数量的数据包的情况下，我们提供了一个类似的结果，在系统中的最大数量的进程，以往任何时候都并发。
Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (1) it should provide constant throughput, wasting as little time as possible; (2) it should require few failed access attempts, minimizing the amount of wasted effort; and (3) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it can suffer subconstant throughput under bursty traffic, and it is not robust to adversarial disruption.The goal of this article is to “fix” exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an online, worst-case fashion. We present a relatively simple backoff protocol, Re-Backoff, that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process.Re-Backoffis also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable forDtime slots, Re-Backoffprovides the following guarantees. Fornpackets, the expected number of access attempts for successfully sending a packet isO(log2(n+D)). For the case of an infinite number of packets, we provide a similar result in terms of the maximum number of processes that are ever in the system concurrently.