BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1332
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: On the Robustness of Herlihy's Hierarchy
AUTHOR:: Jayanti, Prasad
DATE::  March 1993
PAGES:: 33
ABSTRACT::
A wait-free hierarchy maps object types to levels in $Z^{+} \cup \{ \infty \}$,
and has the following property: if a type $T$ is at level $N$, 
and $T'$ is an arbitrary type, then there is a wait-free implementation of 
an object of type $T'$, for $N$ processes, using only registers and objects 
of type $T$. The infinite hierarchy defined by Herlihy is an example of a 
wait-free hierarchy. A wait-free hierarchy is robust if it has the 
following property: if $T$ is at level $N$, and  $\cal S$ is a finite set of 
types belonging to levels $N$ -- 1 or lower, then there is no wait-free 
implementation of an object of type $T$, for $N$ processes, using any number 
and any combination of objects belonging to the types in $\cal S$. 
Robustness implies that there are no clever ways of combining weak shared 
objects to obtain stronger ones.

Contrary to what many reserchers believe [AGTV92, AR92, Her91a], we prove 
that Herlihy's hierarchy is not robust. We then define some natural variants 
of Herlihy's hierarchy, which are also infinite wait-free hierarchies. With 
the exception of one, which is still open, these are not robust either. We 
conclude with the open question of whether non-trivial robust wait-free 
hierarchies exist. 
END:: CORNELLCS//TR93-1332
BODY::
On the Robustness of
Herlihy's Hierarchy*
Prasad Jayanti
TR 93-1332
March1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*Research supported by NSF grants CCR-8901 780 and CCR-91 02231,
DARPNNASA Ames grant NAG 2-593, grants from the IBM Endicott Programming
Laboratory and Siemens Corp.
On the
robustness
hierarchy*
of llerlihy's
Prasad Jayanti
Department of Computer Science, Cornell University
Ithaca, New York 14853, USA
prasadCcs.cornell.edu
Abstract
A wait-free hierarchy maps object types to levels in Z+ u?co1 and has the following
property: if a type T is at level N, and T' is an arbitrary type, then there is a wait-
free implementation of an object of type T', for N processes, using only registers and
objects of type T. The infinite hierarchy defined by Herlihy is an example of a wait-free
hierarchy. A wait-free hierarchy is robust if it has the following property: if T is at level
N, and 8 is a finite set of types belonging to levels N --H 1 or lower, then there is no
wait-free implementation of an object of type T, for N processes, using any number and
any combination of objects belonging to the types in 8. Robustness implies that there
are no clever ways of combining weak shared objects to obtain stronger ones.
Contrary to what many researchers believe [AGTv92, AR92, Her91a], we prove
that Herlihy's hierarchy is not robust. We then define some natural variants of Herlihy's
hierarchy, which are also infinite wait-free hierarchies. With the exception of one, which
is still open, these are not robust either. We conclude with the open question of whether
non-trivial robust wait-free hierarchies exist.
o+Research supported by NSF grants CCR-8901780 and CCR-91o2231, DARPA/NASA Ames grant NAG-
2-593, grants from the IBM Endicott Programming Laboratory and Siemens Corp.
1 Introduction
A concurrent system consists of asynchronous processes communicating via typed shared
objects such as registers, test&sets, and queues. Since any given system supports only a
limited set of object types in its hardware, other useful types will need to be implemented
in software. Thus, implementing an object of a given type using objects belonging to a
given set of types is a fundamental problem. To be useful, implementations must guarantee
(inearizabitity [HW9O]: concurrent accesses on an implemented object must appear to take
effect in some sequential order. One way to ensure linearizability is to implement shared
objects using critical sections [CHP71]. This approach however is not fault-tolerant: the
crash of a process while in the critical section of an implemented object can permanently
prevent the remaining processes from accessing the object. This lack of fault-tolerance led
to the concept of wait-free implementations [Lam77J. An implementation is wait-free if
every process can complete every operation on the implemented object in a finite number of
its own steps, regardless of the execution speeds of the remaining processes. In particular, if
object 0 is built using a wait-free implementation, then the crash of some processes cannot
disable the remaining processes from completing their operations on 0.
How feasible are walt-free implementations? It is known that registers are too weak to
implement1 even a 2-process consensus object, i. e., a consensus object that is accessed by
at most two processes [LAA87, CIL87J. Test&sets and i-bit read-modify-write objects can
implement a 2-process consensus object, but not a 3-process consensus object [LAA87]. 3-
valued read-modify-write, on the other hand, can implement an N-process consensus object,
for all N. These results indicate that object types differ in their ability to support wait-free
synchronization, and that there may be a way of ordering them accordingly. This issue was
addressed in a seminal paper by Herlihy [Her88, Her91bJ. Foliowing are some important
definitions and results in [Her9ib].
1. For every object type T, an object of type T can be implemented for N processes
using only registers and N-process consensus objects. This is the universality result
of Herlihy.
2. For every N > 1, (N + 1)-process consensus object cannot be implemented using just
registers and N-process consensus objects.
3. The consensus number of a shared object 0 is the maximum number N such that an
N-process consensus object can be implemented using just 0 and (any number of)
registers. Define a hierarchy of shared objects such that 0 is at level N if and only if
its consensus number is N. This will be referred to as Herlihy's hierarchy.
As an obvious consequence of the universality result, Herlihy's hierarchy has the fol-
lowing important property: if an object 0 of type T is at level N, then for every object type
an object of type T' can be implemented for N processes using just registers and objects
of type T. We will call any hierarchy with this property a wait-free hierarchy. Thus, in a
stands for "wait-free implementation".
2
1Hereafter "implementation"
wait-free hierarchy such as Herlihy's, if an object 0 of type T is at level N, we can immedi-
ately infer that arbitrary wait-free synchronization among N processes is feasible using just
registers and objects of type T. Notice that this definition allows 0 to be at level N even if
arbitrary wait-free synchronization among more than N processes is feasible using registers
and objects of the type of 0. Thus, the level of an object in a wait-free hierarchy does
not reflect the object's full potential; it is only a lower bound on the extent to which the
object can support arbitrary wait-free synchronization. To understand the exact potential
of objects, we define a tight wait-free hierarchy. In such a hierarchy, an object 0 is at level
N if N is the maximum number of processes for which arbitrary wait-free synchronization
is feasible using registers and objects of the type of 0.
What other properties are important in a hierarchy? We argue below that robustness is
one. A hierarchy is robust if for every object 0, the following holds: if 0 is at level N, then
it is impossible to implement 0 for N processes using any number and any combination of
objects at levels N --H 1 or lower. Robustness guarantees that there are no clever ways of
putting weak objects together to implement a strong one. We now present an example to
illustrate the significance of robustness in analyzing the power of shared primitives. Consider
two systems S1 and S2. Suppose that S1 supports only registers and testasets,and S2
supports only registers with 3-register assignment. Herllhy showed that arbitrary wait-
free synchronization is impossible for 3 or more processes in S1, and for 5 or more processes
in S2. What impllcations do these results have on a third system S3 which supports both
testasets, and registers with 3-register assignment? In particular, can we conclude,
based on just the above results, that arbitrary wait-free synchronization among 5 processes is
still impossible? We can, provided that Herllhy's hierarchy is robust. Otherwise we cannot.
More generally, if Herlihy's hierarchy is robust, the consensus number of a set of objects,
belonging (possibly) to different types, is just the maximum of the consensus numbers of the
individual objects in the set. Thus, robustness reduces the difficult problem of analyzing the
power of a combination of shared objects to the simpler problem of analyzing the power of
the individual objects. On the other hand, if robust wait-free hierarchies do not exist, then
there is a possibility of combining weak objects to implement strong ones. In particular,
it opens up the possibility of implementing universal objects from non-universal objects!
Thus, from a pragmatic point of view, it would also be interesting to prove that robust
wait-free hierarchies do not exist.
Is Herllhy's hierarchy robust? A study of this question with respect to common object
types, such as register, testtset, fetchtadd, queue, compareaswap, and sticky-bit,
does not present any evidence to the contrary. In fact, many prominent researchers have
attributed robustness to Herllhy's hierarchy [AGTV92, AR92, Her9la]2 We prove that it
2[AGTV92j states ?An object has a consensus number k if k is the maximum number of processes for
which the object can be used to solve the consensus problem. Thus objects with higher consensus number
cannot be deterruinistically implemented by employing objects with lower consensus numbers."
[AR92] states ?n fact, Herlihy [Her88] describes a full hierarchy of atomicity assumptions, and proves
that atoms of a higher class cannot be implemented by those of a lower class, in a wait-free fashion in the
deterministic setting."
[Her9laj states "Elsewhere [17, 15], we have shown that any object X can be assigned a consensus number,
which is the largest number of processes (possibly infinite) that can achieve consensus asynchronously [13j by
3
is not robust. More specifically, we present an object type Tap with the property that k
objects of this type, together with registers, can implement a (k + 1)-process consensus
object, but not a (k + 2)-process consensus object. In particular, one T5? object, with
registers, can implement a 2-process consensus object, but not a 3-process consensus object.
Thus, by definition, a Tap object has a consensus number of 2, and is consequently at
level 2 in Herlihy's hierarchy. However, since multiple Tap objects, with registers, can
implement a consensus object for arbitrarily large number of processes, it follows from
Herlihy's universallty result that for all types T and all N, an object of type T can be
implemented for N processes using just registers and Tap objects. Together with the fact
that a T8? object is at level 2, this implies that Herlihy's wait-free hierarchy is not robust.
Does there exist a robust wait-free hierarchy? We do not know the answer yet. However,
we define three natural variants of Herlihy's hierarchy, which are also infinite walt-free hier-
archies. We prove that two of these are not robust.3 The third hierarchy, whose robustness
is still open, has the following property: if it is not robust, then there is no robust wait-free
hierarchy. We believe that resolving the robustness of this hierarchy is an important open
problem in wait-free synchronization.
This paper is the first to formallze and study robustness. The technical arguments
involved in proving the impossibility result that k Tap objects cannot implement a (k +2)-
process consensus object are novel. Traditional bivalency arguments are inadequate to prove
such lower bounds.
2 Informal model
A concurrent system consists of processes and shared objects. We write ....... ,P?;O1,... , Om)
to denote a concurrent system consisting ofprocesses P1,..., Pn and shared objects..... 0m
Besides a unique name, every object has two attributes: a type and a positive integer which
denotes the maximum number of processes which may apply operations on that object.
We say that 0 is an N-process object if N is the maximum number of processes which
may apply operations on 0. The type specifies the behavior of the object when operations
are applied sequentially, without overlap. More precisely, an object type T is a tuple (OP,
RES, G), where OP and RES are sets of operations and responses respectively, and G is a
directed finite or infinite multi-graph in which each edge has a label of the form (op, res)
where op E OP and res E RES. We refer to G as the sequential specification of T, and the
vertices of G as the states of T. lutultively, if there is an edge, labeled (op, res), from state
a to state a', it means that applying the operation op to an object in state a may change
the state to a' and return the response res.
applying operations to a shared X. It is impossible to construct a non-bloclcing implementation of any object
with consensus number n from objects with lower consensus numbers in a system of n or more processes,
although any object with consensus number n is universal (it supports a wait-free implementation of any
other object) in a system of n or fewer processes."
3In proving this, we show the following result which is interesting in its own right. There exist two types
such that (i) Even 2-process consensus cannot be solved using objects of either type, and (il) N-process
consensus (for all N) can be solved using the two types of objects together.
4
A sequence S = (opi,resi),(op2,res2),..., (opt, rest) is legal from state a of T if there
is a path labeled S ill G from the state a. T is deterministic if for every state a of T
and every operation op E OP, there is at most one edge from a labeled (op, res) (for some
res E RES). T is non-deterministic otherwise. T is total if for every state a of T and every
operation op E OP, there is at least one edge from a labeled (op, res) (for some res E RES).
In this paper, we restrict our attention to total types.
An N-process object 0 of type T supports the set of procedures Apply(Pi, op, 0),
for all 1 < i < N and op E OP(T). A process P invokes operation op on object 0
by calling Apply(P, op, 0), and executes the operation by executing this procedure. The
operation completes when the procedure terminates. The response for an operation is the
value returned by the procedure. We denote the event of P invoking operation op on 0 by
inv(P, op, 0), and the event of 0 returning a response v to P by resp(P, v, 0).
The type of an object, by itself, is not sufficient to characterize the behavior of the
object in the presence of concurrent operations. To characterize such behavior, we use the
concept of linearizability [HW90]. Roughly speaking, linearizability requires every opera-
tion execution to appear to take effect instantaneously at some point in time between its
invocation and response. We make it more precise below.
Consider a concurrent system S = (Pi,P?,...,Pn;Oi,O?,... , Om). A configuration
of S is a tuple consisting of the states of the processes P1,... , Pn and the states of the
objects ..... . O?. An execution E of S is a sequence C0,e0,C1,e1,C2,e2,..., where Cj's
are configurations of S, C0 is the initial configuration, e?'s are events, and Cj+1 is the
configuration that results when event e? occurs in configuration Ci. The history in E is the
subsequence of events in . The history of object 0 in E is the subsequence of events of
o in E. If e and e' are two events in a history H, we write e <H e' if e is before e' in
H. A complete operation in H is a palr of events in H --H an invocation and its matching
response. An incomplete operation in H is an invocation that has no matching response.
H is complete if it has no incomplete operations. If op and op' are two operations in II, we
write op <H op' if the response of op is before the invocation of op' in H. Two operations
op and op' are concurrent if neither op <H op' nor op' <H op. H is sequential if it has no
concurrent operations.
Let H be a history of object 0. A linearization of H is a complete sequential history
S with the following properties:
1. S includes every complete operation in H.
2. Let inv(Pi, op, 0) be an invocation in H with no matching response (and is thus an
incomplete operation). Then, either S does not include this incomplete operation or
S includes a complete operation (inv(P?, op, 0), resp(i?, v, 0)) for some v.
Intuitively, this captures the notion that some incomplete operations in H had a
visible" effect, while the others did not.
3. S includes no operations other than the ones mentioned in 1 or 2.
4. For all operations op, op' in S, if op <H op' then op <s op.
5
Thus, the order of non-overlapping operations in H is preserved in S.
Notice that a given history may have several linearizations. A history H of object 0 is
linearizable with respect to type T, initialized to state a, if H has a linearization which is
legal from state a of T.
Processes are asynchronous: there are no bounds on the relative speeds of processes.
Furthermore, a process may crash: a process may stop at an arbitrary point in an execution
and never take any steps thereafter. A process is correct in an execution  if it does not
crash in E. We assume that every correct process has an infinite number of events in an
infinite execution. An object 0 is wait-free in an execution E if either (i)  is finite, or (ii)
every invocation on 0 from a process that does not crash in E has a matching response.
Let T be an object type and fl = (T1,T2,...) be a (possibly infinite) list of (not
necessarily distinct) object types. Let ? = (a1,a2,...) be a list where a? is a state of type
Ti. An implementation of T, initialized to state a, from (, ?) for N processes is a function
1(01,02,...) such that if 01,02,... are N-process objects of type T1,T2,..., initialized to
states a1,a2,..., respectively, then 0 = 1(01,02,...) is an N-process object of type T,
initialized to a. Intuitively, 1(01,02,...) returns a set of procedures Apply(Pj, op, 0), for
1 < i < N and op E 0P(T). Apply(Pi, op, 0) specifies how process Pj should "simulate"
the operation op on 0 in terms of operations on 0i, 02We say 0 is a derived object
of the implementation I, and Oi, 02,... , O? are the base objects of 0.
We say that I is an implementation of T, initialized to state a, from a set S of types
for N processes if there is a list  = (T1,T2,...) of types and a list ? = (a1,a2,.. .) of states
such that Tj E S, a? is a state of Tj, and I is an implementation of T, initialized to a, from
(, ?) for N processes. We say that a type T has an implementation from a set S of types
for N processes if for every state a of T, there is an implementation of T, initialized to a,
from s for N processes.
An implementation is wait-free if it has the foliowing property: if all base objects are
walt-free in an execution E, then the derived object is walt-free in . Hereafter when we
write "implementation", it stands for "walt-free implementation"
We now define consensus and register --H two object types that appear frequently
in this paper. Type consensus supports two operations: propose(O) and propose(1). The
sequential specification of consensus is in Figure 1. Erom the specification, it is clear that a
consensus object 0 has the foliowing properties: (i) If 0 returns a response v, then there is
an invocation of propose(v) preceding this response, and (ii) 0 returns the same response
to all operations. These are known as the validity and agreement properties, respectively, of
a consensus object. Sometimes we refer to the consensus problem for processes P1, ..... .
This problem is stated as foliows. Each process Pj is initially given a binary input Vj. Each
correct process Pi must eventually decide a value di such that (i) di E fvi,v2,... , vn), and
(li) Vi < i,j < n : di = dj. These two conditions are commonly referred to as the valldity
and agreement requirements of the consensus problem.
Type register supports the operations fread) u fvrite(v)Iv > OJ, and has the se-
quential specification given in Figure 2.
6
op = (propose(v)jv E (0, 1))
Object State:
X E (1,0,1)
propose(v)
ifX = I then
X := v
return(X)
Figure 1: Sequential specification of consensus
OP= (read)u (write(v)Iv > 0)
Object State:
XE(O,1,2,...)
read()
return(X)
write(v)
X := v
return(ack)
Figure 2: Sequential specification of register
3 Hierarchy Preliminaries
A hierarchy of shared types is a function that maps object types to levels in (1,2,3,...) u
(co). An object type T is at level tin hierarchy h if h(T) = 1. A hierarchy is non-trivial
if it has at least two non-empty levels. An object type T is universal for N processes if
for every type T', there is an implementation of T' from (T, register) for N processes. T
is universal (for oo processes) if for all N, T is universal for N processes. A hierarchy h
is a wait-free hierarchy if for all T, h(T) = N implies that T is universal for N processes.
Thus, in a wait-free hierarchy, the level of T is a lower bound on the number of processes
for which T (together with registers) can support arbitrary wait-free synchronization. The
following proposition is immediate from the definition.
7
Proposition 3.1 If h is a wait-free hierarchy, and h' is a hierarchy such that VT : h'(T) <
h(T), then h'is a wait-free hierarchy.
Proposition 3.2 If h is a wait-free hierarchy, then h(register) = 1. Thus, level 1 of any
wait-free hierarchy is non-empty.
Proof There exist object types (for example, queue) which have 110 implementation from
register for two or more processes [Her91bJ. Thus, register must be at level 1 ill ally
wait-free hierarchy.			0
Prom Proposition 3.1, it is clear that there can be "slack" in a wait-free hierarchy.
This motivates us to define tightness. A wait-free hierarchy h is tight if for every wait-free
hierarchy h' and every type T, h(T) > h'(T). A wait-free hierarchy is fully-refined if for all
levels k E ?1,2,3,.. 1 u ?ooJ, there is some type ill level k. A wait-free hierarchy h is robust
if for every type T and every finite set S of types, if h(T) = N and VT' E S : h(T') < N,
then there is no implementation of T from S for N processes. The reader should note the
difference between tightness and robustness. The trivial wait-free hierarchy which maps
every object type to level 1 is obviously robust, but not tight. The wait-free hierarchy ?
(to be defined soon) is tight, but it is not known whether it is robust.
In the remainder of this section, we define some natural wait-free hierarchies, and high-
light some simple properties of these hierarchies. 111 the following definitions, the subscript
indicates whether the definition allows just 1 or many objects of the argument type. The
superscript r indicates that the definition allows the use of registers.
1. h1(T) = maximum number of processes for which a consensus object can be imple-
mented using just a single object of type T. If there is no such maximum, then
h1(T) = 00.
2. hr1(T) = maximum number of processes for which a consensus object can be imple-
mented using just a single object of type T and any number of registers. If there is
no such maximum, then hr1(T) = 00.
Notice that this is Herlihy's hierarchy.
3. h1(T) = maximum number of processes for which a consensus object can be imple-
mented using any number of objects of type T. If there is no such maximum, then
h1(T) =00.
4. h?(T) = maximum number of processes for which a consensus object can be imple-
mented using any number of objects of type T and any number of registers. If there
is no such maximum, then h?(T) = 00.
Proposition 3.3 Each of h1, h?1, h1, ? is a fully-refined wait-free hierarchy.
Proof Herlihy's universality result trivially implies that these are wait-free hierarchies.
That these are fully-refined follows from the easy observation that Vh E ?h1, hr1, h1, ?J and
8
op = fpropose(v)Iv E fo, 1))
Object State:
X E fI,o,1)
NEfQ1,2,...1
propose(v)
N := N+ 1
if X = I then
X := v
if N <k then
return(X)
else return(I)
Figure 3: Sequential specification of k-cons
k E fl,2,3,.. jufoo), h(k-cons) = k. (See Figure 3 for the definition of the type k-cons.)
0
Proposition 3.4 ?(T) = N < Co if and only if T is universal for N processes, but not
for N + 1 processes. ?(T) = Co if and only if T is universal.
Proposition 3.5 If h is a tight wait-free hierarchy, then h = ?. In other words, ? is the
unique wait-free hierarchy which is tight.
The hierarchy ? is uniquely important in the study of robust wait-free hierarchies. To
formally state this, we need a definition. Let a = (1i,12,...) be a finite/infinite sequence
such that 1 = li < 12 < 13... and li E f1,2,3,..j U fCoJ. We say g is a coarsening of
hierarchy h with respect to a if, for all object types T, we have:
1. If l? < h(T) < 1i+1, then 9(T) =
2. If l? < h(T) and l? is the last element of a, then g(T) = li.
3. If h(T) = Co and a is infinite, then g(T) = Co.
Intuitively, levels l? ... (1i+i --H 1) in h are lumped into level l? of g, causing levels
(li + 1) ... (1i+i --H 1) to be empty in g. We say 9 is a coarsening of a hierarchy h if there is
a a of the form 1 = li < 12 < 13... such that 9 is a coarsening of h with respect to a. it is
obvious that if h is a wait-free hierarchy, so is every coarsening of h.
Theorem 3.1 If h is a robust wait-free hierarchy, then h is a coarsening of h?.
9
Proof Assume that h is a robust walt-free hierarchy, and is not a coarsening of ?. Let
(7= (11,12,...), where 1 = li < `2 < 13... are all the non-empty levels of h. Define g to be
the coarsening of ? with respect to (7. From our assumption that h is not a coarsening of
?, it follows that h $ g. Thus, there is a type T such that h(T) $ g(T). Let m = h(T)
and n = g(T). By definition of g, a level k of g is non-empty if and only if level k of h
is non-empty. Together with m $ n, this implies that there exist types T' and T", each
different from T, such that g(T') = m and h(T") = n. Since m $ n, we are left with two
cases to consider.
1. m < n.
Since g(T) = n, it follows that ?(T) > n. Thus, by Proposition 3.4, T is universal for
n processes. In particular, there is an implementation of T" from fT, registerj for
n processes. Since h(T) = m < n = h(T"), h is not robust. This is a contradiction.
2. m> n.
From the above, 9(T') = m. Thus, level m of g is not empty. This, together with
m > n, implies that n < h?(T) < m. This implies, by Proposition 3.4, that T is
not universal for m processes. Since h(T) = m, it follows that h is not a walt-free
hierarchy. This is a contradiction.
This completes the proof of the theorem.			0
What can we say about the robustness of h1, hr1, and h1? This question is addressed
by the following proposition.
Proposition 3.6 Let h E fhi,hr1,h1). If h $ ?, then h is neither tight nor robust.
Proof Proposition 3.5 implies that h is not tight. Theorem 3.1 and Proposition 3.3 imply
that h is not robust.			0
Does one of h1, h?1, and h1 define the same hierarchy as ?? The answer is not easy. For
instance, hr1 differs from ? if and only if there is a type such that multiple objects of this
type (together with registers) can solve consensus among a larger number of processes than
a single object (together with registers) can. Does such a type exist? No common object
type exhibits such a property and, hence, it is a non-trivial question. Similarly, h1 differs
from ? if and only if there is a type such that the use of registers increases the number
of processes for which consensus can be solved using objects of this type. Agaln, common
object types do not exhibit this property, making it difficult to answer whether such types
exist.
In the rest of the paper, we prove that each of h1 , h?1, and h1 differs from ?. Thus,
none of h1 , h?1, and h1 is robust. In particular, h?1, which is the same as Herlihy's walt-free
hierarchy, is not robust. Unfortunately, we do not yet know whether ? or some coarsening
of it is robust. This is an important open question. We hope that the ideas employed in
this paper would provide useful insights.
10
(L-op, L.first)			5L			(L.op, L-first)			(R-op, R-first)
(R-op, L-first)
Figure 4: Object type Taticky
(L-op, R-first)
5R (R-op, R.first)
4 On the robustness of hr1 (Herlihy's hierarchy)
The main result of this section is that h?1 is not robust. We prove this result by presenting
all object type Tsp with the following property: n T8? objects, together with registers, can
implement a consensus object for n + 1 processes, but not for n + 2 processes. This implies
hri(Thp) = 2 and h?(Thp) = 00. Thus, hr1 $ ?, and by Proposition 3.6,hr1 is not robust.
Consider the object type Tsticky ill Figure 4. It supports two operations, L-op and
R-op, and responds with either L-first or R-first. If L-op is applied on a Taticky object
0, initialized to state S1, 0 changes state to SL and returns L-first as the response.
Furthermore, 0 returns L-first to all subsequent operations, reflecting the fact that L-op
was the first operation applied on 0. The behavior is symmetric if, instead of L-op, R-op
was the first operation applied on 0. In essence, the first operation "sticks" to 0 and
determines the response for all operations. Notice that Taticky is similar to the consensus
[Her91bJ and sticky-bit (Plo89] object types.
Now consider the type T8?, a variant of Tsticky, shown in Figure 5. Tsp lacks the
symmetry of Taticky If R-op is applied to a T8? object 0, initialized to S1, R-op sticks to
o as before. However, as soon as R-op is applied for the second time, it "unsticks" and 0
starts behaving as though it had been stuck with L-op all along. The following is a trivial
consequence of the definition of Tsp.
Lemma 4.1 Let 0 be an object of type T8p initialized to Sj. Let E be an execution in
which R-op is applied at most once on 0. Then, the following statements are true in E.
1. If r1 and r2 are the responses to any two operations on 0, then r1 = r2.
?. If 0 returns a response D-first (D E ?i, RJ), then an invocation of D-op precedes this
response.
4.1 Implementing consensus from fThp, registerj --H upper bound
In this section, we show how to implement a consensus object for n processes using (n --H 1)
T8p objects and 2(n --H 1) registers. Our implementation is recursive. Let I? denote the
11
(L.op, L-first)
(R-op, L-first)
(L-op, L-first)			(R-op, R-first)
(R-op, L-first)
Figure 5: Object type Tap
5R (L-op, R-first)
On?i: consensus object for P1, P2,.
O??: Tap object, initialized to Sj
L, 1?: binary registers
Apply(Pi,proposeVj,On) (for 1 <i < n --H 1)
1.
2.
3.
4.
L := Apply(Pi, propose Vj? On--Hi)
if Apply(Pi, L-op, O?p) = Lfirst
return(L)
else return(R)
Pn--Hi, derived from 1n--H1
Apply(Pn,proposeVn,On)
R := Vn
if Apply(Pn, R-op, O?p) = L-first
return(L)
else return(R)
Figure 6: Implementing consensus with Tap and register
implementation of consensus from (Tap,register) for processes P1,P2,...,Pj. The base
case is to deriveI?, implementation ofconsensus for the single process P1, and is trivial:
if O? is a derived object of I?, Apply(P1, propose vi, Oi) simply returns v1. The recursive
step of deriving In from 1n--Hi is presented in Figure 6.
Lemma 4.2 The implementation 1n in Figure 6 is a correct implementation of consensus
from (Tap,register) for processes Pi,P2,... , Pn. 1n requires (n --H 1) objects of type Tap
and 2(n --H 1) registers.
Proof We prove the correctness of In by induction. The following is the induction hy-
pothesis: for 1 < j < n --H 1 I? is a correct implementation of consensus for processes
Pi, P2,. . . , P1. The base case, namely, that Ii (described above) is a correct implementa-
tion of consensus for Pi, is obvious. The induction step is proved through several simple
12
claims. Let On be a derived object of 1n Consider an execution E of the concurrent sys-
tem (P1,P2,... , Pn; On). Assume that each Pi executes Apply(Pi, propose Vi, On) at most
once in E.4 We make the following claims about . The proof of each claim follows its
statement.
Cl. For D E fL, R), the following holds:
1. Every process that writes the register D, writes the same value V in D.
2. IfD=L,VE(Vl,V2,...,Vn?l1. Otherwise, V=Vn.
For D = R, the claim is obvious since only Pn writes R. For D = L, the claim follows
from the agreement and vaildity properties of 0n-l
02. Some process completes a write on D before any process receives the response D-first
from O??.
By Lemma 4.1, some process, say Pk, invokes D-op before any process receives the
response D-first. By the implementation, this process Pk will have completed a write
on the register D before invoking D-op on
Consider, for arbitrary i,j and i $ j, the executions of Apply(Pi, propose Vi, On)
and Appiy(Pj, propose Vj, On) in E. By Lemma 4.1, the responses received by Pi and Pj
from Osp (in Statement 2 of their respective executions) are the same. Let D-first be this
response (for some D E fL, R)). Thus, in Statement 3, both Apply(Fi, propose Vi, On)
and Apply(i%, propose Vj, On) read and return the value in the register D. From Claims
C2 and Cl, it follows that both Apply(Pi, propose Vi, On) and Apply(Pj, propose Vi, On)
read the same value V in D and that V E (v1,v2,..., Vnj. Thus, the value returned by
both Apply(Pi, propose Vi, On) and App1y(i?, propose Vj, On) is the same and is from
fvi, v2,..., vn). It is obvious that the implementation is wait-free. Hence the lemma. 0
Corollary 4.1 h?(Tap) = 00.
4.2 Implementing consensus from (Tap, registerj --H lower bound
The main technical result of this section states that any solution to fl-process wait-free
consensus using Tap objects and registers requires at least n --H 1 Tap objects, regardless of
how many registers are available. We prove this result by reducing the "i-resilient consensus
problem for n processes communicating via registers5,, to the "wait-free consensus problem
for n processes communicating via registers and (n --H 2) Tap objects". The former problem is
impossible to solve [LAA87]. Hence the impossibility of the latter. The reduction is based
on the novel concept of k-trep implementations.
4This is not a limitation for the following reason. After Pi executes Apply(Pi, pwpose Vj On) once it
can record the return value in its local variable. Thereafter, when Pi needs to apply a propose operation on
0n it may simply return the value of this local variable as the response. This strategy works because On
is a consensus object, and therefore must return the same response to every invocation.
5A protocol is k-resilient if it meets the problem specification despite the crash of k or fewer processes.
13
4.2.1 k-trap implementations
An implementation for processes P1, ..... ., Pn is a k-trap implementation if every de-
rived object O of the implementation has the following property: in any execution of
(P1,P2,... , P?; 0), regardless of the relative execution speeds of processes, all but up to k
correct processes will be able to eventually complete their operations on 0. In other words,
0 appears wait-free to all but up to k correct processes.
We now contrast k-trap implementations with the familiar wait-free, non-blocking,
and critical-section based implementations. Critical-section based implementations and
non-blocking implementations (for n processes) are both (n --H 1)-trap implementations. A
critical-section based implementation is (n --H 1)-trap because the crash of a single process in
the critical section blocks the remaining (n --H 1) processes. A non-blocking implementation
is (n --H 1)-trap because repeated execution of operations by one process could cause the
remaining processes to block. The converse does not hold: an (n --H 1)-trap implementation
does not guarantee the properties of either a critical-section based implementation or a non-
blocking implementation. To see this, suppose that exactly one process, say P, attempts
to access the object, and suppose that P is correct. In the case of a critical-section based
implementation or a non-blocking implementation, P is guaranteed to complete its operation
on the object. But in a k-trap implementation (k > 1), P may block. Finally, note that a
0-trap implementation is the same as a wait-free implementation.
The following lemma establishes the utility of k-trap implementations in proving lower-
bounds.
Lemma 4.3 Let T be any object type such that for every state a of T, there is a i-trap
implementation I? of T, initialized to a, from register for n processes. Then, any wait-
free implementation of consensus from ?T, register) for n processes requires at least n --H1
objects of type T (regai?less of how many registers it uses).
Proof Suppose that the lemma is false, and there is a wait-free implementation J of
consensus from ?T, register) for n processes such that J requlres only n--H2 objects of type
T, initiallzed to states ai,a2,... , an?2 ofT, and m registers (for some m> 0). Consider the
protocol P in Figure 7. Clearly, processes communicate exclusively via registers in protocol
P. We argue below that ? solves the consensus problem for processes Pi,P2,..., Pn even
if (at most) one of the processes may crash. By the impossibility result in [LAA87], such a
protocol does not exist. Hence the lemma.
We claim that at most (n --H 2) processes block on 0. This follows from the following
facts:
1. n --H 2 base objects of 0 are 1-trap. So at most one process blocks on each of these.
2. No process blocks on the remaining base objects of 0, the registers R1,R2,... , Rm.
3. 0 is derived from a wait-free implementation.
14
1. For 1 < i < n --H 2, use I?? to implement an object 0? of type T initiallzed to state ?.
2. Use J to implement a consensus object O from Oi, 02,... , 0n--H2 and registers
R1,R2,. .
3. Let D be a 3-valued register initialized to I.
4.			_ _
For 1 <i < n, let Vj be the binary input value of process Pj for consensus. Process Pi
executes the following procedure. We require that statements 1 and 2 are executed in
a fair manner.
cobegin
1.
2.
coend
D Apply(Pi, pmpose Vj? 0)
repeat until (D $ I).
decide D
Figure 7: i-resilient consensus protocol P for n processes
Therefore, if at most one of P1,P2,... , Pn crashes, there is still one process, call it
Pk, that neither crashes nor blocks on 0. This process Pk eventually writes the response,
call it V, returned by Apply(Pk, propose Vk, 0) in register D. Since 0 satisfies valldity,
we have V E ?vi,v2,... , Vn). Since 0 satisfies agreement, no process ever writes a value
different from V in register D. Since Statements 1 and 2 are executed in a fair manner,
every non-crashing process eventually reads V and decides V. In other words, P solves the
consensus problem for P1, ..... . , P? even if at most a single process may crash. 0
4.2.2 i-trap implementation of Tap
Recall that T8p has three states - 5j, 5L, and 5R We now present a i-trap implementation
of T8p initiallzed to Si, and 0-trap implementations of T8p initiallzed to 5L or 5R. These
implementations use only registers as base objects. Thus, by Lemma 4.3, we have the
desired lower bound.
A i-trap implementation of Tap, initialized to Si, from register for n processes is
presented in Figure 8. This implementation is subtle. We present below an informal and
intuitive argument of its correctness before proceeding to give the formal proof. Consider
0, a Tap object derived from this implementation. Let H be a history of 0, and let first-op
denote the first operation to complete in H. There are two cases. Case (1) corresponds
to first-op being an L-op operation. Consider the linearization 5 which includes only the
complete operations in H and sequences them in the order of their completion times. Thus,
15
Apply(Pi,L-op,0)
return(L-first)
..... . nJ: binary (i-writer, n-reader) registers initialized to 0
1.
2.
3.
4.
Apply(Pi,R-op,0)
if (Vk : R[k]= 0) then
R[i] 1
repeat until (?j <i : R[j]= 1)
return(L-first)
Figure 8:1-trap implementation of Tap, initialized to S1, from register
first-op, which is an L-op operation, becomes the the first operation in S. Furthermore,
the response of every operation in S is L-first (this is obvious from the implementation).
From the sequential specification of Tap in Figure 5, it is obvious that S is legal from
the state 5j of Tap. Now consider Case (2), which corresponds to first-op being an R-op
operation. The key observation is that if first-op, which is an R-op operation, completed in
H, then by our implementation, there must be another R-op operation, call it blocked-op,
from a different process which is concurrent with first-op and is blocked. Let us pretend
that, although incomplete, blocked-op has indeed taken effect in H, and has R-first for its
response. Consider the linearization S which sequences blocked-op first, first-op second, and
the remaining complete operations in H in the order of their completion times. (blocked-
op can be linearized before first-op since these two operations are concurrent.) Thus the
first operation in the linearization S is a R-op operation with R-first as the associated
response. The second operation in the linearization is also an R-op operation, and has
L-first as the associated response. The remaining operations in the linearization have L-
first as their response. From the sequential specification of Tap in Figure 5, it is obvious
that this linearization S is legal from the state Sj of Tap. Hence the correctuess of our
implementation. We formalize the above arguments and present a more rigorous proof of
correctness below. The proof is based on a series of claims.
Claim 4.1 The implementation is i-trap.
Proof Clearly, a correct process Pi blocks if and only if the repeat... until loop (Statement
3 of Apply(Pi, R-op, 0)) never terminates. By Statement 2, such a Pi will have written the
value 1 into R[ij.
Suppose that the claim is false, and two correct processes Pi and Pj (assume j < i) block
on 0. It follows that R[i] = R[jJ = 1 and each of Pi and i? is caught in the repeat... until
loop that never terminates. Process Pi eventually notices that R[j] = 1, and since j < i, Pi
quits the repeat... until loop, and returns L-firsL This contradicts the assumption that Pi
16
blocks on 0.
0
The next claim asserts that if a process Pi successfully completes an R-op operation
on 0, then a different process Pj is already blocked, unable to complete its R-op operation
on 0.
Claim 4.2 Let E be an execution of (P1, ..... ., P?; 0), and 11 be the corresponding his-
tory. Suppose that H contains the two events --H an invocation e::nv = inv(Pj, R-op, 0)
and its matching response e?r.es = resp(P?, L-first, 0). Then H contains an invocation
e,t.nv = inv(Pi, R-op, 0) such that
1. e;?v <H e?r,U, and
2. e,i.nv has no matching response in H.
Proof The proof of this claim is based on the following observations:
01. The predicate ?k : R[k]= 1 is stable: that is, if it holds in some configuration of an
execution, it holds in every subsequent configuration of that execution. Furthermore,
this predicate must hold before a response can occur to any invocation of R-op.
The first part of this observation follows from the fact that once a 1 is written to a
register, it is never changed. The second part is obvious from Statements 1 and 2 of
the implementation.
02. In H, let k be the smallest integer such that Pk has an invocation ekinv = inv(P?,
R-op, 0) and Pk writes a 1 in R[k]. Then etknv has no matching response in H.
To see this, notice that after writing a 1 in R[kJ, Pk enters the repeat... until loop.
This loop never terminates in H because of our premise that k is the smallest integer
such that Pk writes a 1 in R[k]. Thus Pk does not return from Apply(Pk, R-op, 0).
03. In H, if a process Pk writes 1 in R[k] after an invocation elknv = inv(P?, R-op, 0) and
before its matching response, then ekinv <H e1res.
Suppose not. Then er?es <H e?knv. After the invocation etknv, when Pk executes State-
ment 1 of the procedure Apply(Pk, R-op, 0), the guard Vk : R[kJ= 0 evaluates to
false (by 01). Thus Pk returns the response L-first without writing into R[kj. This
contradicts the premise that Pk writes 1 into R[k] after the invocation e?knv and before
its response.
To complete the proof of the claim, let 5 be the set of processes that invoke R-op on 0
and write 1 into a register in the execution E. Since H contains a response event e?jCJ?by
01, 5 is non-empty. Let j be the smallest integer such that i? E 5. By 02, i?'s invocation
e;.nv of R-op on 0 has no matching response in H. By 03, e;.nv <H er?es. Hence the claim.
0
Claim 4.3 Let E be an execution of ??.,..., P?; 0), and 11 be the history of 0 in E. H
is linearizable with respect to Tsp, initialized to state 5j.
17
Proof ff H has no response events, then the claim is trivial: the empty sequence is a
linearization of H and is legal from state Sj of Tap. Assume, therefore, that H has one or
more response events. Let er?es = resp(Pi, L-first, O) be the earliest response in H. Let
e::nv be the invocation whose matching response is er?es. There are two cases:
Case 1.
e:.nv = inv(Pi, L-op, 0)
This corresponds to the case in which the first operation to complete is an L-op
operation from process Pi. Define a sequential history S as follows:
1.
2.
S includes all complete operations in H.
If two operations op and op' are in S, op <s op' if and only if response of op
precedes the response of op' in H.
It is obvious that (i) 5 is a linearization of H, and (ii) 5 is legal from the state 5j of
Tap.
Case 2. einv = inv(Pj, R-op, 0)
This corresponds to the case in which the first operation to complete is an R-op from
process Pi. By Claim 4.2, there is an invocation e;.nv = inv(P,, R-op, 0) such that
e;nv <H e:.es and eijnv has no matching response in H. Define a sequential history 5
as follows:
1.
2.
3.
5 includes all complete operations in Ir, and the operation (e;??v, e;.es), where
e,r.ea = resp(i?, R-first, 0).
The operation (e3i.nv, e??8) precedes all other operations in 5.
ff op and op' are operations in 5 different from (e;?, e,r.es), op <5 op' if and only
if the response of op precedes the response of op' in i?.
It is easy to verify that (i) 5 is a linearization of H, and (ii) 5 is legal from the state
5j of Tap.
Hence the claim.			0
Lemma 4.4 Figure 8 presents a i-trap implementation of Tap, initialized to Si, from
register for processes Pi,.2... . ,
Proof Follows from Claims 4.1 and 4.3.			0
Lemma 4.5 Figure 9 presents a 0-trap (wait-free) implementation of Tap, initialized to 5R,
from register for processes P1,P2,..., Pn.
Proof Let E be an execution of (P1,P2,... , P?; 0), and let HR and H0 be the histories of
objects R and 0, respectively, in E. Let ?R be a linearization of HR, which is legal from
the state 0 of register. For every operation op E ?R. define f(op) as follows:
18
App1y(i?, L-op, O)
if (R = 0) then
return(R.first)
else return(L-first)
R: binary register initialized to 0
Apply(Pi,R-op,0)
R := 1
return(L.first)
Figure 9: 0-trap implementation of Tap, initialized to 5R, from register
ifop = (inv(Pj, read, R), resp(P?, 0, R)) then
f(op) = (inv(Pj, L-op, 0), resp(Pj, R-first, 0))
else if op = (inv(Pj, read, R), resp(P?, 1, R)) then
f(op) = (inv(Pi, L-op, 0), resp(P?, L-first, 0))
else if op = (inv(Fj, write 1, R), resp(P?, ack, R)) then
f(op) = (inv(Pj, R-op, 0), resp(P?, L-first, 0))
Define a sequential history ?o as follows:
1. For every operation op E ?R, include f(op) in ?o.
2. 1fop, op' E ?R and op <?R OP', then f(op) <?o f(op').
It is easy to verify that ?o is a linearization of `lo, and is legal from the state 5R of Tap.
0
Lemma 4.6 Figure 10 presents a 0-trap (wait-free) implementation of Tap, initialized to
5L, from register for processes Pi,P2,... ,
Proof Obvious.			0
Lemma 4.7 Any wait-free implementation of consensus from ?Tap,register) for n pro-
cesses requires at least n --H 1 objects of type Tap.
Proof Follows from Lemma 4.3, and Claims 4.4, 4.5, and 4.6.			0
Corollary 4.2 hri(Thp) = 2.
Proof By Lemma 4.2, h?1(Thp) > 2. By Lemma 4.7, h?1(Thp) <2. Hence the result.			0
19
Apply(Pj, L-op,0)			Appiy(Pj, R-op,0)
return(L-first)			return(L.first)
Figure 10: 0-trap implementation of Tap, initialized to SL
Theorem 4.1 hr1 is neither tight nor robust.
Proof Follows from Proposition 3.6 and Corollaries 4.1 and 4.2.
Theorem 4.2 h1 is neither tight nor robust.
0
Proof From the definitions of h1 and hr1, it is obvious that, for all types T, hi(T) < hr1(T).
In particular, hi (Tap) < hri(Thp) = 2 < oo = ?(Thp). Thus, by Proposition 3.6, h1 is
neither tight nor robust.			0
5 On the robustness of hm
The main result of this section is that h1 is not robust. We prove this result by presenting
an infinite family Tnkd, k E (2,3,4,...) u (oo), of object types with the following properties:
1. There is an implementation of consensus from (Tnkd, register) for k processes, but
not for k + 1 processes.
2. There is no implementation of consensus from Tnkd for two processes.
Property (1) implies that ?(Tnkd) = k. Property (2) implies that h (Tk ) --H 1. Thus,
h1 $ h?, and by Proposition 3.6, h1 is not robust.6 This result is significant in the following
sense. Registers by themselves are too weak to solve even 2-process consensus. So are
objects. Combining these two types, however, lets us solve consensus among any number
of processes!
The object type Tknd is specified in Figure 11. In this specification, choose(S) is assumed
to choose an element from set 5 non-deterministically and return it. Notice that upset and
ahead[i] are stable: once true, they remain true. Similarly, once decision E (0, 1), it does
not change.
6A aingle member of the Tnkd family is sufficient to establish that h1 is not robust. The existence of an
entire family shows that there is not even a coarsening of hi which is non-trivial and robust.
20
51. Tnkd supports operations in fop(i)Ii = (0, 1)) u (give-decision(i, b)li E (0, 1), 6 E
(true, false)).
S2. The response for op(0) or op(1) is always ack. The response for give-decision(--H, --H)
is either 0 or 1.
S3. The state of Tnkd is represented by the variables no, ni, fl2d : integer; decision E
(I,0,1); ahead[O..1], upset : boolean. Informally, no,ni,n?d count the number of
executions of op(0), op(1), and give-decision, respectively. The variable ahead[i]
is set to true if flj > 0 and n-? = 0 when give-decision(i, --H) is executed. The
variable upset is set to true if one of the following happens: (i) op(1) is executed
more than once (op(O) may be executed any number of times without upsetting a Tnkd
object); (il) give-decision is executed more than k times; (iii) give-decision(i, --H)
is executed with no prior execution of op(i); (iv) give-decision(i, true) is executed
with no prior execution of op(i); (v) give-decision(i, false) is executed and ahead
fli = true. If upset, a Tnkd object returns 0 or 1 non-deterministically to an invocation
of give-decision. If not upset, it sets decision irrevocably and non-deterministically
(if not already set) to 0 or 1 such that ?decision > 0, and returns decision. See 55
below for a formal sequential specification of Thkd.
S4. The state of Thkd corresponding to (n0 = ni = n9? = 0; decision = I; ahead[0..1J =
upset = false) is known as the fresh state. The states of Tknd are only those that are
reachable from the fresh state by the following specification.
55. The sequential specification of Thkd is as follows:
op(i)
flj := flj + 1
if n1 > 1 then upset := true
return(ack)
/? i E (0,1) *1
give-decision(i,other-is-ahead) /* i E (0, 1), other-is-ahead: boolean */
n9? := ?2d+ 1
if(fli > 0An-?= 0) then ahead[i] := true
if (n2d> k) v (ni = 0) v (ahead[? A ?other-is-ahead) v(n-?= 0Aother-is-ahead) then
upset := true
if upset then
return(choose((0, 1)))
else if decision = I then
decision := choose((jin? > 0))
return(decision)
Figure 11: Object type Tnkd
21
5.1 consensus from ?Tnkd, register) --H an implementation
In this section, we show, for k E f2, 3,.. .) u ?oo), how to implement a consensus object for
k processes using only Tnkd objects and registers. Our implementation is recursive. Let 1?k
denote the implementation of consensus from fTnkd, register) for processes Pi,P2,... ,
The base case is to derive 10k, implementation of consensus for an empty set of processes,
and is vacuous. The recursive step of deriving Ink from Ink?i is presented in Figure 12.
7k
The Implementation n works as follows. Processes ... . Pn split into two groups, G0
and &1. Group G0 has P1... Pn-i, and group G1 has just Pn. Processes P1... Pn--Hi do
consensus among themselves (recursively) and announce the outcome in R[oJ. Process Pn
announces its input value in R[1J. The rest of the protocol resolves which of the two groups
is the winner. If Co wins, every process decides the value in R[0]. Similarly, if G1 wins,
every process decides the value in R[1J. The object Ond is used to determine the winner
of the two groups. Processes P1... Pn-i perform the operation op(O) on Ond. Then they
set the register R'[oJ to inform process Pn that op(0) has been executed on Ond. Process
Pn, on the other hand, performs op(l) on Ond, and then sets R'[1] to inform processes in
G0 that op(l) has been executed. Processes then perform the give-decision operation.
The return value determines the winning group. For this strategy to work correctly, the
arguments of the give-decision operation must be such that the Ond object does not get
upset. We urge the reader to understand how the registers R'[o.. 1] are used to ensure that
Ond does not get upset. Finally, if Ond returns v, a process assumes that the group Gv won
and decides the value in R[v].
Lemma 5.1 For 1 <n < k the implementation Ink in Figure 12 is a correct implementa-
tion of consensus from fTnkd, register) for processes Pi,P2,..., Pn.
Proof Sketch By induction. Assume that Ink?i is correct. Let On be a derived object
of the implementation in Figure 12. Consider an execution E of the concurrent system
(P1,P2,..., Pn; On) in which every process Pj has invoked App1y(P?,propose Vj, On) exactly
once, and executed it to completion. The key claim is that Ond is not upset in E. This
follows from the following simple observations:
1. op(l) is executed only once.
2. For v E fo, 1), op(v) is executed before executing give-decision(v, --H).
3. give-decision is executed no more than n times. Since n < k, give-decision is
executed no more than k times.
4.
Suppose op(v) is ahead of op(?v). That is, the operations op(v) and then give-decision(v, --H)
are completed before the first invocation of op(v). Then, the use of the registers
.1] in the implementation 1k 1 guarantees that when a process invokes
give-decision(--Hv, other-ahead), the second parameter, namely, other-ahead, is true.
22
baseobjectsoftheimplementationInk
Pi,P2,...,Pn--Hi,derived fromInk?i
to thefresh state
On?1: consensus object for
Ond Tnkd object, initialized
R[O..1]: binary registers
R'[O..1]: boolean registers, initialized to false
localvariablesofprocessPi
di, winner? E (0, 11
other-aheadi: boolean
Apply(Pi,proposeVj,On) (for 1 <i < n --H 1)
1.
2.
3.
4.
5.
6.
7.
di := Apply(Pi,proposevi,On?1)
R[OJ := di
Apply(Pi,op(O),Ond)
R'[oj := trne
other-ahead? :=
winner? :=
Apply(Pi,give-decision(O,other-aheadi), Ond)
return(R[winner?])
Apply(Pn,propose Vn, On)
dn := Vn
R[1] := dn
Apply(Pn,op(i),Ond)
R'(1J := trite
other-aheadn :=
winnern :=
APPly(Pn,give-decision(1,other-aheadn), Ond
return(R[winnern])
Figure 12: Implementing consensus from (Tnkd, registerj
23
5.
Suppose no process completes the operation op(v) before some process invokes
give-decision(?v,other-ahead). Then the use of the registers R'[o. .1] in the imple-
mentation Ink?i guarantees that the second parameter of give-decision, namely,
other-ahead, is false.
Since Ond is not upset in , by the specification of Tnkd, we have:
1. Every give-decision operation on Ond returns the same binary response. Let
winner E (0, 1? denote this response.
2. Some process P, invokes op(winner) before Ond returns winner for the first time to
agive-decisionoperation.
From the implementation, it is clear that I>, writes the value dj in R[winner] before invoking
op(winner). Furthermore, once a value is written by a process into a register R[oJ or R[lj,
the value of that register never subsequently changes. For R[oj, this follows from the
agreement property of Onk?1, and for R[1J, this follows from the fact that only Pn writes
R[1] and writes it only once.
The above implies that for all i, Apply(Pi, propose Vj? On) returns dj. Thus, On satisfies
agreement. If j = n, then dj = dn = Vn, and thus, On satisfies validity. If j ? n, by the
validity of 0n--Hi, dj E (v1,v2,... , vn?i). Thus, On satisfies validity. It is obvious that the
implementation is wait-free. This concludes the proof of correctness of ink 0
5.2 consensus from fTnkd,registerj --H an impossibility result
In this section, we prove that Tnkd objects and registers do not suffice to implement a
consensus object for k + 1 processes. This impossibility result follows from a straight
forward bivalency argument. The intuition behind why this impossibility result holds for
k + 1 processes, but not for k processes, is as follows. As we have seen, a Tnkd object supports
two kinds of operations: op and give-decision. The operation op(i) does not return any
useful information to the invoking process. This is due to the fact that the response of op(i)
is always ack. The operation give-decision does return useful information, but only to
the first k invocations of the operation. Thereafter, its response is non-deterministic and
hence is not helpful. Thus, k processes may gain useful information from a Tnkd object, but
k + 1 processes cannot. We now proceed to prove the impossibility result.
Let Tkd be a deterministic object type whose specification is defined by replacing every
expression of the form choose(S) in Figure 11 by min(S).7 Thus, Tkd is a deterministic
restriction of Tnkd Hence, if a history of an object is linearizable with respect to Tkd, then it
is a fortiori linearizable with respect to Tnkd We prove below that Tdk objects and registers
do not suffice to implement a consensus object for k + 1 processes. This trivially implies
that Tnkd objects and registers cannot implement a consensus object for k + 1 processes.
7min(s)isthe minimum element in set S.
24
As mentioned, the proof uses a simple bivalency argument. Since bivalency arguments
are standard, our definitions and the proof are informal. A configuration C of a concurrent
system is v-valent (for v E fO, 1)) if there is 110 execution from C in which v is decided
by some process. In other words, once the system is in configuration C, no matter how
processes are scheduled, no process decides v. A configuration is monovalent if it is either
0-valent or 1-valent. A configuration is bivalent if it is not monovalent. If E is a finite
execution of a system S started in configuration C, E(C) denotes the configuration of S at
the end of the execution . For the purposes of this section, a step of a process P consists
of invoking an operation on an object 0, receiving the response from 0, and making an
appropriate change in its state.
Lemma 5.2 Forall k E f2,3,...), there is no implementation of consensus from frdk, register)
for k + 1 processes.
Proof Assume I(Oi,02,.. , O?) is an implementation of consensus from fTkd, register)
for processes P1,P2,..., Pk+1. Let O=1(Oi,02,... , O?). Consider the concurrent system
S=(P1,P2,... , P?+i; O). Let Co be the initial configuration of S. Assume that in C0, each
process Pj is about to execute App1y(i?,propose Vi, 0). Furthermore, assume that there are
l,m (1< l,m < k+ 1) such that vt = 0 and Vm = 1.
When P1 runs by itself from C0, the validity and walt-freedom of 0 requlre that P1
decide vi = 0. Similarly, when Pm runs by itself from Co, it decides Vm = 0. Thus, C0 is
bivalent. Let  be an execution from Co such that (1) C?it = (C0) is bivalent, and (2)
For all Pi, if Pi takes a step from C?it, the resulting configuration is monovalent. Let Sv
be the set of processes whose step from C?it results in a v-valent configuration. Since C?it
is bivalent, neither S0 nor S1 is empty. Furthermore, So fl Si = ? and So U Si I = k + 1 > 3
(since k > 2). Without loss of generality, assume that ISo > 2 and ISi I > 1. In particular,
let So = fP?i,P?2,...,i?) and Si = (Pi1,P21,...,Ps1), where r >2 and s > 1.
By a standard argument, the enabled step of every process in configuration C?it must
be on the same base object 0 of 0. Furthermore, agaln by a standard argument, 0 is not a
register. Thus, the enabled step of every process in configuration Ccrit is on 0, an object of
type Tkd. Let 802 and sii denote the enabled steps of i?? and P11, respectively, in configuration
C?it. Consider the following scenarios So and Si, each starting from the configuration C?it.
o+ In Scenario So, P20 takes the step 502. Then, P11 takes a step. Let D0 be the resulting
configuration. Clearly D0 is a 0-valent configuration.
o+ In Scenario Si, P11 takes the step sii Then, ??2 takes a step. Let D1 be the resulting
configuration. Clearly D1 is a 1-valent configuration.
Processes P20 and P11 have to distinguish Scenario So from Scenario Si, since they must
decide 0 in (every extension of) So, and decide 1 in (every extension of) Si. Observe that
unless the operation applied by P20 (resp. P11) in step 502 (resp. sj) is a give-decision
operation, it must eventually apply a give-decision operation on 0 in order to distinguish
So from Si. Thus, we extend Scenarios So and Si as follows:
25
If the operation applied by i? On 0 ill step 502 is not a give-decision operation,
run F02 (ill both scenarios) exactly until i? completes a step in which it applies a
give-decisionoperation on 0.
If the operation applied by P11 on 0 in step sli is not a give-decision operation,
run i? (in both scenarios) exactly until i\' completes a step in which it applies a
give-decisionoperation on 0.
A process P E ??....., Pk+iJ --H ?i)i[?, PO2, i?Y has to distinguish Scenario So from Scenario
Si, since P must decide 0 in (every extension of) So, and decide 1 in (every extension of) Si.
Observe, however, that P cannot distinguish So from Si until it applies a give-decision
operation on 0. Thus, we extend Scenarios So and Si as follows:
o+ For each P E ....... , Pk+1J --H ?????, P?2, P11), run P (in both scenarios) exactly until
P completes a step in which it applies a give-decisionoperation 011 0.
We make the following observations: (1) The process i? is in the same state in Scenarios
So and Si. (2) Every base object except 0 is in the same state ill So and Si (3) In both So
and Si, a give-decisionoperation is applied on 0 at least k times (once by each process
in ???...., Pk+11 --H fi?), in the execution from C?it). The second observation, together
with the specification of Tdk, implies that every subsequent give-decisionoperation on 0
returns 0 in either scenario. Extend Scenarios So and Si by letting i?? run by itself. By the
above observations, ? cannot distinguish whether it is running in So or Si Yet it must
decide 0 in So and 1 in Si This is impossible. Hence the lemma. 0
Corollary 5.1 ForallkEf2,3,..ju?oo),?(Tnk?)=k
Proof Follows from Lemmas 5.1 and 5.2.
0
5.3 h1 is not robust
In this section, we prove that h (Tk ) --H 1. Thus, h1 is different from ? and, hence, is not
robust. We begin with a simple technical lemma that will be useful in proving h (Tk ) --H 1.
The lemma states that it is trivial to implement Tnkd, initialized to any state different from
the fresh state. In the following, let a[v] denote the value of state variable v in state a.
Lemma 5.3 Let a be any state of Tnkd different from the fresh state. Figure 13 is an
implementation of Tnkd, initialized to a, from ?.?
Proof If a is different from the fresh state, then it is easy to verify that
(a[decision] E ?0, 1)) V (a[n0] > 0) V (a[n1] > 0) V a[upsetj. From this and the specification
of Tnkd, the correctness of the implementation is obvious. 0.
5Thus, the implementation ?qrnres no base objects, not even registers.
26
op(i)
return(ack)
give-decision(i, b)
if a[decision] E (0, 1) then
return(a[decision])
else if (?[ipsetJ v o[noj > 0) then
return(O)
else return( 1)
Figure 13: Implementing Tnkd, initialized to a non-fresh state ?
The following lemma states that it is impossible to implement a consensus object for
two processes using just Tnkd objects. Intuitively, Tnkd objects are so weak that a process
cannot use these objects to leave its "foot marks" behind. Thus, if a process P0 runs first,
and then a different process P1 runs, P1 does not realize that P0 ran before it started.
This can cause P1 to decide a value which is not consistent with the decision of P0. The
proof below formalizes this argument. The details of the argument are subtle due to the
non-determinism of the Tnkd objects.
Lemma 5.4 For all k E (2,3,.. .J u (co), hI(Tnkd) = 1.
Proof To prove this lemma, we must show that it is impossible to implement a consen-
sus object for two processes using just Tnkd objects. We show this by contradiction. Let
I(Oi, 02,..., On) be an implementation of consensus from Tnkd for processes Po and P1,
which is resource optimal: i. e., if T is another implementation of consensus from Tnkd for
two processes, then I, requires at least n base objects. From Lemma 5.3, it follows that
every base object of I is initialized to the fresh state.
Consider a derived consensus object 0 of the implementation I. Let 01,02,..., O? be
the base objects of 0. In other words, 0=I(Oi,O2,.. , On). In the following, we present
two scenarios, So and Si, which are indistinguishable to P1, but require P1 to take different
actions.
In Scenario So, Po invokes Apply(Po, propose 0,0) and executes it to completion. (Exe-
cution to completion is possible since I is a wait-free implementation.) Assume that during
the execution of Apply(Po,propose 0,0), every base object behaves like a Tkd object. That
is, the history of each base object in the execution of Apply(Po, propose 0, 0) is linearizable
with respect to Tdk. We will refer to this as Assumption Al. By the validity property of
0, Apply(P0, propose 0,0) returns 0. Let S be the set of base objects which are in the
fresh state in Scenario So at the completion of Apply(Po, propose 0,0). Continue Scenario
So, and begin Scenario Si, by letting P1 invoke Appiy(P1,propose 1,0) and run by itself in
either scenario. (See Figure 14 for a depiction of Scenarios So and Si.) Assume that each
27
Scenario s0			P0executes
Apply(Po,propose0,0)
Scenario s1
TIME
Figure 14: Scenarios So and Si
P1 executes
Apply(Pi,propose1,0)
P1 executes
Apply(P1,propose1,0)
base object ill S behaves deterministically, consistent with Tkd, ill both scenarios. We wffl
refer to this as Assumption A2. We prove the following statement inductively: the base
objects in ?O1,O2,... , --H S can choose among the non-deterministic alternatives (when
applicable) such that for all i > 0, P1 cannot distinguish So from Si ill i steps. The base
case for i = 0 is trivial. To prove the induction step, assume the hypothesis for i < m.
Consider the (m+ 1)8? step. Let oper be the operation that P1 performs in this step ill
Scenario 5o, and let 0 be the base object 011 which it performs oper. From the induction
hypothesis and the fact that the implementation is deterministic, it follows that P1 performs
oper on 0 ill its (m+ 1)st step ill Scenario Si too.
Suppose oper E (op(0), op(l)J. Then, the response is ack in either scenario. Thus, So
and Si remaln indistinguishable to P1 after m+ 1 steps. Hence the induction step.
We make a case analysis to prove the
Suppose that oper is give-decision(--H, --H).
induction step.
Case 0. 0 E S
o is fresh in both So and Si just before the invocation of Apply(Pi,propose1,0).
For So, this follows from the definition of S, and for Si, from the fact that every base
object is initialized to the fresh state. By Assumption A2, 0 behaves deterministically
(consistent with Tkd) in both scenarios. The above facts, together with induction
hypothesis, guarantee that (i) 0 is in the same state in both scenarios at the end of
m steps of P1, and (ii) 0 returns the same response to oper in both scenarios. Thus,
So and Si remaln indistinguishable to P1 after m+1 steps. Hence the induction step.
28
Case 1. Case 0 does not apply and the following holds: In at least one of S0 and St,0is upset
in the first m+ 1 steps of P1.
Let Sj be a scenario in which 0 is upset in the first m + 1 steps of P1. By the
specification of Tnkd, 0 is free to return 0 or 1 to oper ill Scenario Si. Suppose that 0
uses this freedom and returns the same response to oper ill Si as it does ill 5r Then
So and St remain indistinguishable to P1 after m+ 1 steps. Hence the induction step.
Case 2. Neither Case 0 nor Case 1 applies. In other words, 0 is not fresh ill So just before
the invocation of Apply(P1,propose1,0) and, ill both So and St, 0 is not upset at
the end of m+ 1 steps of P1.
We prove the induction step by contradiction. Assume that it is not possible to keep
Scenarios 5o and St indistinguishable to P1 at the end of m+ 1 steps. We will refer
to this as Assumption A3. We arrive at a contradiction after a series of claims. Let
? and ff1k denote the state of 0 at the end of k steps of P1 ill Scenarios So and St
respectively.
Ci. ?[n9d] = 0. In other words, P1 does not apply a give-decisionoperation on
o in its first m steps.
Suppose that the claim is false. Let k < m be the smallest integer such that
oik[ng?] = 1. That is, give-decision is executed on 0 for the first time by
P1 in its kth step in Scenario St. Since 0 is not upset in St, this implies
that ?1k[decision] E ?0,1J, and this value is returned by 0 in the kth step of
P1 in St. By inductive hypothesis, the same value aik[decisionj is returned by
o in the k?h step of P1 even in So Since 0 is not upset in So, this implies
that 00k[decision] = aik[decisionj. Since decision is irrevocable, it follows that
00m[decisionj --H ok[decision] = 01k[decision] = 01m[decision] E fO, 1J. Since 0 is
not upset in either scenario, the responses oom[decision] and oim[decision] of 0 to
oper in Scenarios So and St, respectively, are identical. Thus, So and St remain
indistinguishable to P1 after m+ 1 steps. This contradicts Assumption A3.
C2. There is a v E (0,1) such that 01m[nv] > 0 and 0i?[n?vi = 0. In other words, P1
executes op(v), but not op(?v) in its first m steps in St.
Suppose oim[no] = 01m[ni] = 0. Then, by the specification of Tnkd, when P1 applies
oper = giv?decision(--H,--H) in the (m + 1)st step in St, it upsets 0. This
contradicts the case we are considering. Suppose 01m[noJ > 0 and 01m[n1] > 0.
Since oim[n,dJ = 0 (by Cl), by the specification of Tnkd, 0 is free to return either
o or 1 in St. Suppose that 0 uses this freedom and returns the same response to
oper in St as it does in So. Then So and St remain indistinguishable to P1 after
m+ 1 steps. This contradicts Assumption A3.
C3. P1 executes op(v) on 0 at least once in its first m steps in So.
Follows from C2 and the induction hypothesis.
C4. oper =give-decision(v,false).
Suppose oper = give-decision(?v,--H) or oper =--H give-decision(v,true). Since
0i?[nv] = 0 (by 02), 0 will be upset in St when oper is invoked in the (m+ 1)st
step. This contradicts the case we are considering.
29
C5. ?[ahead?v]] = false.
Suppose %m[aheadrvi] = true. Then, when P1 executes oper = give-decision(v,false)
(guaranteed by C4) in its (m + 1)st step ill So, it upsets 0. This contradicts the
case we are considering.
06. v = 1 implies ?00[n9dJ = 0. In other words, if v --H 1 then Po never executed a
give-decisionoperation on 0 in So.
Suppose v = 1 and Po executed give-decision(1,--H) on 0 in So. Since 0
is not upset in So, it follows that Po executed op( 1) on 0 before executing
give-decision(1,--H). By 03 and the assumption that v = 1, P1 executed op(1)
in 5o. Thus op(1) was executed at least twice on 0 in So. By the specification
of Tnkd, 0 would be upset in So. This contradicts the case we are considering.
Suppose v = 1 and Po executed give-decision(O,--H) on 0 in So. Since 0
is not upset in So, it follows that Fo executed op(O) on 0 before executing
give-decision(O,--H). By 05 and the assumption that v = 1, o?m[ahead[O]] =
false. This implies that Po executed op(l)on 0 before executing give-decision(O,--H).
By 03 and the assumption that v = 1, Pi executed op(l)in So. Thus op(l) was
executed at least twice on 0 in 5o By the specification of Tnkd, 0 would be upset
in So. This contradicts the case we are considering.
07. v = 0.
Suppose v = 1. Then, we can infer: (1) aim[ngd] = 0 (by 01), (2) aom[ngd] = 0
(by 01, induction hypothesis, and 06), (3) airn[ni] > 0 (by 02), (4) a0m[niJ > 0
(by 03). These four facts, together with the specification of Thkd, imply that 0
is free to return 0 to oper in both 5o and Si. Suppose that 0 does this. Then
5o and Si remain indistinguishable to Pi after m + 1 steps. This contradicts
Assumption A3.
08.
09.
o returns 0 to oper (in the (m + 1)8t step of P1) in Scenario Si
02 and 06 imply that aim [n0] > 0 and aim[nij = 0. Further, by the case we are
considering, 0 is not upset in the first m + 1 steps of Pi in Scenario Si. The
above facts imply that the only legal value that 0 can return to oper is 0.
If Po executed give-decision(1,--H)on 0 (in 5o), it did so only after executing
op(O) on 0.
Suppose Po executed give-decision(1,--H)on 0 (in 5o) Since 0 is not upset in
So, this implies that P0 executed op(1) on 0 before executing give-decision(1,--H).
If P0 did not execute op(O) before executing give-decision(1,--H),then the ex-
ecution of give-decision(O,--H)would set ahead[1] to true. This, together with
the fact that ahead[1] is stable, implies that aom[ahead[1]] = true. This contra-
dicts the conjunction of 05 and 07.
Every execution of the operation give-decision(--H,--H)on 0 by P0 in Scenario
So returns the response 0.
Consider the earliest execution e of give-decision(w,--H)on 0 by Po in So. If
w = 1, 09 implies that P0 executes op(O) before e. If w = 0, the fact that 0 is
not upset in So implies that P0 executes op(O) before e. Thus, we conclude that
010.
30
Cli.
P0 executes op(O) before e. This, together with Assumption Al, implies that e
returns 0. From this and the fact that 0 is not upset in So, it follows that every
execution of give-decision(--H, --H) on 0 in So returns the response 0.
P0 never executes give-decision(--H, --H) on 0 (in 5o).
Suppose that the claim is false. Then, from 010 and the fact that 0 is not upset
in So, it follows that 0 returns 0 to oper in the (m + 1)st step of P1 in Scenario
So. Thus, by 08, 5o and Si remain indistinguishable to P1 after m + 1 steps.
This contradicts Assumption A3.
We have: (1) O1m[no] > 0. This follows from C3 and 07. (2) oom[no] > 0. This follows
from (1) and induction hypothesis. (3) aon'[ng?] = 0. This follows from Cl, induction
hypothesis, and Cli. From (2), (3), and the specification of Tnkd, it is clear that 0 is
free to return 0 to oper (in the (m + 1)st step of P1) in Scenario So. Suppose that it
does. Then, by 08, 5o and Si remain indistinguishable to P1 after m + 1 steps. This
contradicts Assumption A3. Hence the induction step.
This completes the proof of the induction step.
Since I is a wait-free implementation, Apply(Pi,propose 1, 0) terminates in So after a
finite number of steps, returning some value vat E (0, 1). Since Si is indistinguishable to
P1 from So, Apply(P1,propose 1,0) terminates in Si after the same number of steps, also
returning vat. If vat = 0, validity of consensus is violated in Si. If vat = 1, agreement of
consensus is violated in So. Thus, I is not a correct implementation, a contradiction. 0
Theorem 5.1 h1 is neither tight nor robust.
Proof Follows from Proposition 3.6, Corollary 5.1, and Lemma 5.4.
6 Conclusion
0
it is well known that shared primitives, depending on their type, vary widely in their ability
to support inter-process synchronization. Recent research focussed on analyzing the power
of individual primitives. in this paper, we ask whether, from our understanding of the power
of the individual primitives, we can infer the power of a set of primitives. For instance, is it
impossible to implement a universal primitive from non-universal primitives? The answer
is not clear. it is conceivable that clever protocols for such implementations exist. Besides
being of theoretical interest, these issues have implications to multi-processor architectures.
To make a systematic study of these issues possible, we define the property of robustness for
wait-free hierarchies. Contrary to popular belief, we show that Herlihy's wait-free hierarchy
is not robust. We also show that some natural variants of Herlihy's hierarchy are also not
robust. This raises the obvious question of whether there is a non-trivial robust wait-free
hierarchy at all. We do not know the answer yet. However, we observe that such a hierarchy,
if it exists, is either ? or some coarsening of it. Thus, further research on the structure
31
of ? is essential to resolving this open question. As explained in the paper, the answer
to this question, regardless of whether it is affirmative or negative, has useful implications.
We close with the conjecture that ? is not robust.
Acknowledgement
I had innumerable discussions with my advisor Sam Toueg on this subject. They were
very helpful in crystalizing my ideas, and in discovering some of these results. The "swap
object" that Jon Kleinberg and Sendhil Mullainathan showed me helped me discover Tsp.
I am grateful to Sam, Jon, and Sendhil for sharing their insights with me. I thank Thshar
Chandra for reading parts of this paper and providing helpful comments. Aparna helped
me with typing. Little Sucharita never complained the travel between home and school, no
matter what time of the night and how cold.
References
[AGTv92j
[AR92J
Y. Afek, E. Gafni, J. Tromp, and P. Vitanyi. Wait-free test&set. In Proceedings
of the 6th Workshop on Distributed Algorithms, Haifa, Israel, November 1992.
(Appeared in Lecture Notes in Computer Science, Springer-Verlag, No: 647).
Y. Aumann and M.O. Rabin. Clock construction in fully asynchronous parallel
systems and pram simulation. In Proceedings of the 33rl Annual Symposium on
Foundations of Computer Science, October 1992.
[CHP71J P.J. Courtois, F. Heymans, and D.L. Parnas. Concurrent control with readers
and writers. Communications of the ACM, 14(1O):667--H668, 1971.
[C1L87]
[Her88j
B. Chor, A. Israeli, and M. Li. On processor coordination using asynchronous
hardware. In Proceedings of the 6th ACM Symposium on Principles of Dis-
tributed Computing, pages 86--H97, August 1987.
M.P. Herlihy. Impossibility and universality results for wait-free synchroniza-
tion. In Proceedings of the 7th A CM Symposium on Principles of Distributed
Computing, 1988.
[Her9laj M.P. Herlihy. Impossibility results for asynchronous pram. In Proceedings of the
3rd ACM Symposium on Parallel Architectures and Algorithms, July 1991.
[Her9lb] M.P. Herlihy. Wait-free synchronization. ACM TOPLAS, 13(1):124--H149, 1991.
[HW90] M.P. Herlihy and J.M. Wing. Linearizability: A correctness condition for con-
current objects. ACM TOPLAS, 12(3):463--H492, 1990.
M.C. Loui and Abu-Amara. Memory requirements for agreement among un-
reliable asynchronous processes. Advances in computing research, 4:163--H183,
1987.
[LAA87]
32
[Larn77] Leslie Lamport. Concurreut reading and writing. Communications of the ACM,
20(11):806--H811, 1977.
5. Plotkin. Sticky bits and universality of consensus. In Proceedings of the
8th ACM Symposium on Principles of Distributed Computing, pages 159--H175,
August 1989.
[P1o89]
33
