Wait-free synchronization

TLDR

A wait‑free implementation guarantees that any process completes an operation in a finite number of steps regardless of other processes, and constructing such implementations from other objects is a central challenge in concurrent algorithms. The authors aim to develop a general technique to prove that certain objects cannot be wait‑freely implemented from others. They reduce the problem to a consensus protocol and construct a hierarchy of objects that formalizes these impossibility results. The study demonstrates that atomic read/write registers and classical primitives such as test‑and‑set, fetch‑and‑add, and standard message‑passing are computationally weak, yet identifies simple universal objects from which any sequential object can be implemented wait‑freely.

Abstract

A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a concensus protocol, for proving statements of the form, “there is no wait-free implementation of X by Y.” We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: thay cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such as test&set and fetch&add , while more powerful than read and write , are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.