Wait-Free SynchronizationMAURICE HERLIHYDigital Equipment CorporationAu,a,zt-free implementation ofa concurrent data object is one that guarantees that any process cancomplete any operation in a finite number of’ steps, regardless of the execution speeds of the otherprocesses. The problem ofconstructinga wait-free implementation of one data object from anotherlies at the heart of much recent work in concurrent algorithms, concurrent data structures, andmultiprocessor architectures. First, we introduce a simple and general technique, based on reductionto a consensus protocol, for proving statements of the form, “there is no wait-free implementation ofX by Y.” We derive a hierarchy of objects such that no object at one level has a wait-freeimplementation in terms of objects at lower levels. In particular, we show that atomic read/writeregisters, which have been the focus of much recent attention, are at the bottom of the hierarchy:they 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 powerfulthan read andunte, 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 canconstruct await-free implementation of any sequential object.Categories and Subject Descriptors: D.1.3 [Programming Techniques] : Concurrent Programming;D.3.3 [Programming Languages] :LanWage Constructs-abstract data types, concurrent program-rnmg structures; D.4.1 [Operating Systems]: Process Management—concurrency, rnutualexclusiorz,synchronizationGeneral Terms: Algorithms, Languages, VerificationAdditional Key Words and Phrases: Linearlzability, wait-free synchronization1. INTRODUCTIONA concurrent object is a data structure shared by concurrent processes. Algorithmsfor implementing concurrent objects lie at the heart of many important problemsin concurrent systems. The traditional approach to implementing such objectscenters around the use of critical sections: only one process at a time is allowedto operate on the object. Nevertheless, critical sections are poorly suited forasynchronous, fault-tolerant systems: if a faulty process is halted or delayed ina critical section, nonfaulty processes will also be unable to progress. Even in afailure-free system, a process can encounter unexpected delay as a result of aA preliminary version of this paper appeared in the Proceedings of the 7th ACM SIGACT-SIGOPSSymposium on Principles of Distributed Computmg (Aug. 1988), pp. 276-290.Author’s address: Digital Equipment Corporation Cambridge Research Laboratory, One KendallSquare, Cambridge, MA 02139.Permission to copy without fee all or part of this material is granted provided that the copies are notmade or distributed for direct commercial advantage, the ACM copyright notice and the title of thepublication and its date appear, and notice is given that copying is by permission of the Associationfor Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specificpermission.@ 1991 ACM 0164-0925/91/0100-0124 $01.50ACM TransactIons on Programming Languages and Systems, Vol. 11, No 1, January 1991, Pages 124-149Wait-Free Synchronization “125page fault or cache miss, by exhausting its scheduling quantum, or if it is swappedout. Similar problems arise in heterogeneous architectures, where some processorsmay be inherently faster than others, and some memory locations may be slowerto access.A wait-free implementation of a concurrent data object is one that guaranteesthat any process can complete any operation in a finite number of steps, regardlessof the execution speeds on the other processes. The wait-free condition providesfault-tolerance: no process can be prevented from completing an operation byundetected halting failures of other processes, or by arbitrary variations in theirspeed. The fundamental problem of wait-free synchronization can be phrased asfollows:Given two concurrent objects X and Y, does there exist a wait-freeimplementation of X by Y?It is clear how to show that a wait-free implementation exists: one displays it.Most of the current literature takes this approach. Examples include “atomic”registers from nonatomic “safe” registers [18], complex atomic registers fromsimpler atomic registers [4, 5, 16, 23, 25, 26, 29, 31], read-modify-write operationsfrom combining networks [11, 15], and typed objects such as queues or sets fromsimpler objects [14, 19, 20].It is less clear how to show that such an implementation does notexkt. In thefirst part of this paper, we propose a simple new technique for proving statementsof the form “there is no wait-free implementation of X by Y.” We derive ahierarchy of objects such that no object at one level can implement any object athigher levels (see Figure 1). The basic idea is the following each object has anassociated consensus number, which is the maximum number of processes forwhich the object can solve a simple consensus problem. In a system of n or moreconcurrent processes, we show that it is impossible to construct a wait-freeimplementation of an object with consensus number n from an object with alower consensus number.These impossibility results do not by any means imply that wait-free synchro-nization is impossible or infeasible. In the second part of this paper, we showthat there exist universal objects from which one can construct a wait-freeimplementation of any object. We give a simple test for universality, showingthat an object is universal in a system of n processes if and only if it has aconsensus number greater than or equal to n. In Figure 1, each object at level nis universal for a system of n processes. A machine architecture or programminglanguage is computationally powerful enough to support arbitrary wait-freesynchronization if and only if it provides a universal object as a primitive.Most recent work on wait-free synchronization has focused on the constructionof atomic read/write registers [4, 5, 16, 18, 23, 25, 26, 29, 31]. Our results addressa basic question: what are these registers good for? Can they be used to constructwait-free implementations of more complex data structures? We show that atomicregisters have few, if any, interesting applications in this area. From a set ofatomic registers, we show that it is impossible to construct a wait-free implemen-tation of