Boosting Obstruction-Freedom with Low Overhead

Rachid Guerraoui, Michał Kapałka, Petr KouznetsovInfoscience 2006

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.

The modular architecture of the contention management system, illustrating the interaction between the OF algorithm, the Contention Manager, and the Intermittent Failure Detector.

As illustrated in Figure 1, the architecture includes:

  1. The OF Algorithm ($A$): The core logic of the shared object.
  2. The Contention Manager (CM) Module: The logic that decides when to intervene, communicating with the algorithm via try and resign signals.
  3. 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

Abstract

A contention manager is a shared memory abstraction that boosts progress of obstruction-free algorithms. In this paper, we study the problem of the overhead of non-blocking and wait-free contention managers which use the minimal possible information about failures. More specifically, we show that ensuring non-blockingness can be achieved with no overhead and that this is not possible when wait-freedom is to be guaranteed. We prove that ensuring wait-freedom has an inherent overhead that, however, can be made arbitrarily small. This shows an interesting “efficiency gap” separating non-blocking and wait-free implementations. To support our claims we present two modular contention manager implementations, both using the minimal possible information about failures: one that ensures non-blockingness with no overhead, and one that ensures wait-freedom and which overhead can be arbitrarily reduced. Interestingly, these contention managers can be used only as a last resort, and can themselves be combined with more pragmatic ones that provide good average case performance. At the heart of our cost-effective contention managers lies the notion of an intermittent failure detector, which we believe is interesting in its own right. Strictly speaking, this is not a failure de tector in the classical sense, but rather an oracle that provides processes with information about failures (only) in certain executions. In particular, in executions with no contention, and when failure detection is not needed, its overhead is not incurred. We consider two such abstractions, which we show can be implemented with little system synchrony, and describe how they help implement our cost-effective contention managers.
BibTeX
@inproceedings{guerraoui2006boosting,
  author = {Rachid Guerraoui and Michał Kapałka and Petr Kouznetsov},
  title = {{Boosting Obstruction-Freedom with Low Overhead}},
  booktitle = {Infoscience},
  year = {2006},
}

Loading related content...

Figure