Wait-freedom vs. &resiliencyand the robust ness of wait-free hierarchies(EXTENDED ABSTRACT)Tushar Chandra’Vassos HadzilacostPrasad Jayanti$Sam Toueg$1 Background and overviewIn a shared-memory system, asynchronous processescommunicate via typed shared objects, such as regis-ters, test&sets, and queues. The need to implement anobject of one type from objects of other types arisesoften in such systems.Recent research has focussedmostly on wait-free implementations. Such an imple-mentation guarantees that every process can completeevery operation on the implemented object in a finitenumber of its own steps, regardless of whether otherprocesses are fast, slow, or have crashed. From now on,we write “implementation” and “implement” as abbre-viations for “wait-free implementation” and “wait-freeimplement”, respectively. If an implementation is notwait-free, we will explicitly state so.It is known that objects of different types varywidely in their ability to support (wait-free) implemen-tations. For example, using test&set objects, one canimplement any object that is shared by at most twoprocesses [Her91]. In contrast, using compare&swapobjects, one can implement objects of any type thatcan be shared by any number of processes [Her91].Thus, it is natural to ask whether object types can bemapped to levels in a hierarchy, where the level of atype reflects its ability to support wait-free implemen-*IBM T. J. Watson, tushar@watson. ibm. comtUniversity of Toronto, vassos@db. toront o. edu, partiallysupport ed by a grant from the Natural Sciences and EngineeringResearch Council of Canadat Dartmouth College, prasadQcs. dartmouth. edu, supportedby Dartmouth grants 2-01361 and 424820.sco~e~ University, sam~cs. cornell. edu, supported by NSFgrad CCR-9102231and/or sp-ecific permission.PODC 94- 8/94 Los Angeles CA USAm1QQA ACM 0-89791 -654-919410008.$3-50tations. We seek two properties in such a hierarchy:(1) If a type T is at level N, then, for all types T’,one can implement an object of type T’ shared by Nprocesses, using only registers and objects of type T.This property ensures that weak types are not placedat high levels of the hierarchy. (2) If a type Tis at levelN, and $ is a set of types all of which are at lower levelsthan T, then one cannot implement an object of typeT shared by N processes, using any number and anycombination of objects of types in S. This propertyguarantees that there are no clever ways of combin-ing objects classified as weak by the hierarchy (i.e.,objects whose types are at low levels) to implementobjects that are classified as stronger (i.e,, at higherlevels).A hierarchy with Property (1) is known as a waat-free hzerarchy, and a hierarchy with Property (2) isknown as a robust hierarchy [Jay93]. Our interest liesin a robust wait-free hierarchy, one which has both ofthe above properties.The existence of such a hierar-chy is an open question.We know, however, that ifsuch a hierarchy exists, it must be the hierarchy h:(or a coarsening of it) defined as follows: h: maps aset S of types to level N if N is the maximum inte-ger so that an N-consensus object can be implementedusing only registers and objects belonging to types inS [Jay93]. (An N-consensus object allows each of amaximum of N processes to access it by proposinga value; the object returns the same value to all ac-cesses, where the value returned is the value proposedby some process. This object plays a central role inrealising wait-free implementations:Herlihy ’s univer-sal construction shows that using N-consensus objectsand registers one can provide a wait-free implementa-tion of any object that is shared by at most N pro-cesses [Her91].)From the universal construction of [Her91], itfollows that hfi is a wait-free hierarchy. Is h% arobust hierarchy? Equivalently, is h~({T, T’}) =max(h~(T)j h~(T’)) for arbitrary types T and T’?While the general question remains open, this paper334proves that the answer is yes for the restricted casewhere T is N-consensus (and T’is arbitrary). Thus,if an object type (together with registers) is pow-erful enough to“boost” N-consensus into (N + 1)-consensus, then (together with registers) it is alreadypowerful enough to implement (N+ 1)-consensus! Thisresult is the subject of Section 3.Wait-free implementations provide an extremedegree of fault-tolerance. They assure that even if justone process survives, it will be able to complete its op-erations. Researchers have also investigated anotherform of implementations which support a more mod-est degree of fault-tolerance [D DS87, LAA87]. Theseguarantee that correct processes will complete theiroperations, as long as no more thant processes fail,wheret is a specified parameter. Such implementa-tions are called t-reszhent.It is immediate from thedefinitions that wait-freedom is equivalent to (N – 1)-resiliency, where N is the number of processes in thesystem. Using our result that h~({T, N-consensus}) =max(h~(T), N), we prove an important connection be-tween t-resilient and wait-free implementations of N-consensus. We describe this connection and its signif-icance below. (The proof is given in Section 4.)Consider the task of devising a t-resilient imple-mentation of an object shared by N processes, as N de-creases. As the ratio of correct processes on which theimplementation can rely gets smaller, the task seemsto become more and more difficult. For example, a t-resilient implementation which works only when a ma-jority of processes are correct, cannot be used when Nbecomes smaller than 2t + 1. In the limit, when N be-comest+ 1, the task amounts to providing a watt-freeimplementation of the object. Thus, prima faczae,itseems that the ability of a set S of objects to supporta t-resilient implementation of an object shared by Nprocesses is greater than the ability of S to support await-free implementation of that object shared by t + 1processes. In this paper we show that this is not thecase for the N-consensus object. More specifically, weprove that, for any N >t > 1, a set of objects can beused for a t-resilient implementation of N-consensus ifand only if it can be used for a wait-free implementa-tion of(t+ 1)-consensus.The “if” direction of this result is not surpris-ing. To give a t-resilient implementation of consensusamong N processes, we can choose t + 1 of the pro-cesses, have them run the given wait-free implemen-tation of (t + I)-consensus, and write the result intoa register. The