Abstract
Obstruction-free algorithms offer high performance in shared-memory systems but can suffer from livelock during contention. Contention managers (CMs) resolve this but often introduce a constant performance "tax." This paper explores the "efficiency gap" between non-blocking and wait-free progress guarantees. We show that non-blockingness can be achieved with zero overhead in contention-free runs, while wait-freedom requires an inherent, though tunable, cost. We introduce "intermittent failure detectors" (IFDs) as a modular solution to provide these guarantees with minimal overhead.
Introduction
In concurrent computing, obstruction-free (OF) algorithms are popular due to their simplicity and efficiency when processes do not interfere. However, when multiple processes access the same data simultaneously, they can enter a "livelock"—a state where no process makes progress despite continuous activity. Contention Managers (CMs) act as referees to break these cycles, but their reliance on continuous failure detection often creates background overhead even when no contention exists. This research investigates how to design CMs that remain "invisible" during smooth executions.
A Modular Architecture for Progress
To address the overhead problem, the authors propose a modular framework consisting of three distinct layers. This separation of concerns allows the system to only activate expensive progress-boosting mechanisms when they are strictly necessary.
As illustrated in Figure 1, the architecture includes:
- The OF Algorithm ($A$): The core logic of the shared object.
- The Contention Manager (CM) Module: The logic that decides when to intervene, communicating with the algorithm via try and resign signals.
- The Intermittent Failure Detector (IFD) Module: A new abstraction that provides failure information on demand. Unlike traditional detectors, an IFD can be "stopped" and "restarted," only incurring costs when explicitly queried by a stalled process.
The Efficiency Gap
A central finding of this work is the "efficiency gap" between two progress levels. The authors formally prove that non-blocking progress (ensuring at least one process finishes) can be achieved with zero overhead in the absence of contention. In contrast, wait-freedom (ensuring every process eventually finishes) always requires at least one additional step, such as checking a flag, to maintain fairness. This means wait-freedom can never be truly "free," though its cost can be made extremely low.
Intermittent Oracles and Results
The power of this approach lies in the use of intermittent oracles. By making failure detection "queryable" and "stoppable," the overhead becomes proportional to the actual difficulty of the execution rather than a constant background burden. The paper introduces two specific implementations:
- $CM_{nb}$ (Non-blocking): Uses an intermittent $\Omega^*$ detector to guarantee progress with zero overhead in contention-free executions.
- $CM_{wf}$ (Wait-free): Uses an intermittent $\diamond P$ detector. While it cannot have zero overhead, it offers a tunable parameter ($k$). A process can check the CM only once every $k$ steps, allowing developers to trade off the time to resolve contention for higher speed during normal operation.
Conclusion
This paper demonstrates that strong progress guarantees do not necessitate high overhead. By employing intermittent failure detectors and a modular design, contention managers can serve as efficient "last resort" mechanisms. These findings provide a theoretical foundation for building high-performance, robust concurrent systems that only pay for progress guarantees when they are actually needed.
Summary updated