Collaborative Research: Adversarial Contention Resolution

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

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.