Collaborative Research: Adversarial Contention Resolution

对抗性争用解决方案Michael A.Bender，Stony BrookMartin Farach-Colton，Rutgers在作业争夺公共资源的计算机系统中，当两个作业同时请求资源时，据说它们会发生冲突。随机退避仍然是解决此类资源争用的首选方法。Backoff的想法是，每当作业发生冲突时，它都会在某个随机延迟后重试。退避是互联网和其他许多复杂系统运作的核心。鉴于随机化退避所发挥的重要作用，令人惊讶的是，退避的许多方面都没有被理解。到目前为止，大多数分析都集中在相对简单的渠道上的工作到达的统计上。然而，统计到达率的假设危险地忽略了最坏的情况，因为突发和其他病理输入是常见的情况。此外，许多实际的信道并不是简单的。本研究的目的是建立退避算法在关于信道的各种假设下的最坏情况性能的理论。这项研究将以共享内存应用中的争用解决问题为指导，例如事务内存。事务内存应用程序具有多个通道，支持的作业大小相差数量级，可以提供丰富的冲突反馈，并且可以在存在冲突的情况下允许一个作业成功，该研究将为众多具有多个访问通道的应用程序提供坚实的理论基础和性能模型。如果没有这些性能模型，实现可能会表现出不可预测和错误的性能。对于共享内存中事务编程的目标应用程序来说，正确理解争用解决方案是创建可行系统的关键。

Adversarial Contention ResolutionMichael A. Bender, Stony BrookMartin Farach-Colton, RutgersIn computer systems in which jobs contend for a common resource, two jobs are said to collide when they request the resource at the same time.Randomized backoff remains the method of choice for resolving such resource contention. The idea of backoff is that whenever a job collides, it retries after some random delay. Backoff is at the core of how the internet and many other complex systems work.Given the prominent role played by randomized backoff, it is surprising that many aspects of backoff are not understood. To date, most analysis has focused on statistical arrival of jobs on relatively simple channels.The assumption of statistical arrival rates dangerously neglects the worst-case, however, because bursty and other pathological inputs are a common case. Furthermore, many actual channels are not simple.This research aims to develop a theory of the worst-case performance of backoff algorithms under various assumptions about the channel. The research will be guided by contention-resolution problems in shared-memory applications, such as transactional memory. Transactional-memory applications have multiple channels, support jobs sizes that differ by orders of magnitude, may provide rich feedback on collisions, and could allow one job to succeed when there are conflicts.The research will provide a solid theoretical foundation and performance model for the many applications having multiple-access channels. Without these performance models, implementations are likely to exhibit unpredictable and buggy performance. For the target application of transactional programming in shared memory, a proper understanding of contention resolution is on the critical path for creating a viable system.