Boosting Obstruction-Freedom with Low Overhead

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.

Related material