--T
Wait-free synchronization.
--A
A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a concensus protocol, for proving statements of the form, there is no wait-free implementation of X by Y. We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that    atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: thay cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such astest&set and fetch&add, while more powerful than read and write, are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.
--B
Introduction
A concurrent object is a data structure shared by concurrent processes. Algorithms
for implementing concurrent objects lie at the heart of many important
problems in concurrent systems. The traditional approach to implementing
such objects centers around the use of critical sections: only one
process at a time is allowed to operate on the object. Nevertheless, critical
sections are poorly suited for asynchronous, fault-tolerant systems: if a
faulty process is halted or delayed in a critical section, non-faulty processes
will also be unable to progress. Even in a failure-free system, a process can
encounter unexpected delay as a result of a page fault or cache miss, by
exhausting its scheduling quantum, or if it is swapped out. Similar problems
arise in heterogeneous architectures, where some processors may be
inherently faster than others, and some memory locations may be slower to
access.
A wait-free implementation of a concurrent data object is one that guarantees
that any process can complete any operation in a finite number of
steps, regardless of the execution speeds of the other processes. The wait-free
condition provides fault-tolerance: no process can be prevented from completing
an operation by undetected halting failures of other processes, or by
arbitrary variations in their speed. The fundamental problem of wait-free
synchronization can be phrased as follows:
Given two concurrent objects X and Y , does there exist a wait-free
implementation 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 non-atomic "safe" registers [19], complex
atomic registers from simpler atomic registers [4, 5, 16, 23, 25, 26, 29, 31],
read-modify-write operations from combining networks [11, 15], and typed
objects such as queues or sets from simpler objects [14, 18, 20].
It is less clear how to show that such an implementation does not ex-
ist. In the first part of this paper, we propose a simple new technique for
proving statements of the form "there is no wait-free implementation of X
by Y ." We derive a hierarchy of objects such that no object at one level
can implement any object at higher levels (see Figure 1). The basic idea
is the following: each object has an associated consensus number, which is
the maximum number of processes for which the object can solve a simple
consensus problem. In a system of n or more concurrent processes, we show
that it is impossible to construct a wait-free implementation of an object
with consensus number n from an object with a lower consensus number.
These impossibility results do not by any means imply that wait-free
synchronization is impossible or infeasible. In the second part of this paper,
we show that there exist universal objects from which one can construct a
wait-free implementation of any object. We give a simple test for univer-
sality, showing that an object is universal in a system of n processes if and
only if it has a consensus number greater than or equal to n. In Figure 1,
each object at level n is universal for a system of n processes. A machine
architecture or programming language is computationally powerful enough
to support arbitrary wait-free synchronization if and only if it provides a
universal object as a primitive.
Most recent work on wait-free synchronization has focused on the construction
of atomic read/write registers [4, 5, 16, 19, 23, 25, 26, 29, 31].
Our results address a basic question: what are these registers good for?
Can they be used to construct wait-free implementations of more complex
data structures? We show that atomic registers have few, if any, interesting
applications in this area. From a set of atomic registers, we show that it
is impossible to construct a wait-free implementation of (1) common data
types such as sets, queues, stacks, priority queues, or lists, (2) most if not
all the classical synchronization primitives, such as test&set, compare&swap,
and fetch&add, and (3) such simple memory-to-memory operations as move
or memory-to-memory swap. These results suggest that further progress in
understanding wait-free synchronization requires turning our attention from
the conventional read and write operations to more fundamental primitives.
Our results also illustrate inherent limitations of certain multiprocessor
architectures. The NYU Ultracomputer project [10] has investigated architectural
support for wait-free implementations of common synchronization
primitives. They use combining networks to implement fetch&add, a generalization
of test&set. IBM's RP3 [8] project is investigating a similar
approach. The fetch&add operation is quite flexible: it can be used for
semaphores, for highly concurrent queues, and even for database synchronization
[11, 14, 30]. Nevertheless, we show that it is not universal, disproving
a conjecture of Gottlieb et al. [11]. We also show that message-passing
architectures such as hypercubes [28] are not universal either.
This paper is organized as follows. Section 2 defines a model of com-
putation, Section 3 presents impossibility results, Section 4 describes some
universal objects, and Section 5 concludes with a summary.
Consensus Object
Number
read/write registers
test&set, swap, fetch&add, queue, stack
assignment
memory-to-memory move and swap, augmented queue,

Figure

1: Impossibility and Universality Hierarchy
2 The Model
Informally, our model of computation consists of a collection of sequential
threads of control called processes that communicate through shared data
structures called objects. Each object has a type, which defines a set of possible
states and a set of primitive operations that provide the only means to
manipulate that object. Each process applies a sequence of operations to ob-
jects, issuing an invocation and receiving the associated response. The basic
correctness condition for concurrent systems is linearizability [14]: although
operations of concurrent processes may overlap, each operation appears to
take effect instantaneously at some point between its invocation and re-
sponse. In particular, operations that do not overlap take effect in their
"real-time" order.
2.1 I/O Automata
Formally, we model objects and processes using a simplified form of I/O
automata [22]. Because the wait-free condition does not require any fairness
or liveness conditions, and because we consider only finite sets of processes
and objects, we do not make use of the full power of the I/O automata
formalism. Nevertheless, simplified I/O automata provide a convenient way
to describe the basic structure of of our model, and to give the basic definition
of what it means for one object to implement another. For brevity,
our later constructions and impossibility results are expressed less formally
using pseudocode. It is a straightforward exercise to translate this notation
into I/O automata.
An I/O automaton A is a non-deterministic automaton with the following
ffl States(A) is a finite or infinite set of states, including a distinguished
set of starting states.
ffl In(A) is a set of input events,
ffl Out(A) is a set of output events,
ffl Int(A) is a set of internal events,
ffl Steps(A) is a transition relation given by a set of triples
s and s 0 are states and e is an event. Such a triple is called a step,
and it means that an automaton in state s 0 can undergo a transition
to state s, and that transition is associated with the event e.
is a step, we say that e is enabled in s 0 . I/O automata must satisfy
the additional condition that inputs cannot be disabled: for each input event
e and each state s 0 , there exist a state s and a step (s
An execution fragment of an automaton A is a finite sequence s
or infinite sequence s alternating states and events such that
each a step of A. An execution is an execution fragment
where s 0 is a starting state. A history fragment of an automaton is the
subsequence of events occurring in an execution fragment, and a history is
the subsequence occurring in an execution.
A new I/O automaton can be constructed by composing a set of compatible
I/O automata. (In this paper we consider only finite compositions.)
A set of automata are compatible if they share no output or internal events.
A state of the composed automaton S is a tuple of component states, and a
starting state is a tuple of component starting states. The set of events of S,
Events(S), is the union of the components' sets of events. The set of output
events of S, Out(S), is the union of the components' sets of output events;
the set of internal events, Int(S), is the union of the components' sets of
internal events; and the set of input events of S, In(S), is In(S) \Gamma Out(S),
all the input events of S that are not output events for some component.
A triple (s is in Steps(S) if and only if, for all component automata
A, one of the following holds: (1) e is an event of A, and the projection of
To remain consistent with the terminology of [14], we use "event" where Lynch and
Tuttle use "operation," and "history" where they use "schedule."
the step onto A is a step of A, or (2) e is not an event of A, and A's state
components are identical in s 0 and s. Note that composition is associative.
If H is a history of a composite automaton and A a component automaton,
H jA denotes the subhistory of H consisting of events of A.
2.2 Concurrent Systems
A concurrent system is a set of processes and a set of objects. Processes
represent sequential threads of control, and objects represent data structures
shared by processes. A process P is an I/O automaton with output
events invoke(P; op; X), where op is an operation 2 of object X , and input
events res is a result value. We refer to
these events as invocations and responses. Two invocations and responses
match if their process and object names agree. To capture the notion that
a process represents a single thread of control, we say that a process history
is well-formed if it begins with an invocation and alternates matching
invocations and responses. An invocation is pending if it is not followed
by a matching response. An object X has input events invoke(P; op; X),
where P is a process and op is an operation of the object, and output events
res; X), where res is a result value. Process and object names
are unique, ensuring that process and object automata are compatible.
A concurrent system fP is an I/O automaton composed
from processes P
and objects are composed by identifying corresponding invoke and respond
events. A history of a concurrent system is well-formed if each H jP i
is well-formed, and a concurrent system is well-formed if each of its histories
is well-formed. Henceforth, we restrict our attention to well-formed
concurrent systems.
An execution is sequential if its first event is an invocation, and it alternates
matching invocations and responses. A history is sequential if it
is derived from a sequential execution. (Notice that a sequential execution
permits process steps to be interleaved, but at the granularity of complete
operations.) If we restrict our attention to sequential histories, then the behavior
of an object can be specified in a particularly simple way: by giving
pre- and postconditions for each operation. We refer to such a specification
as a sequential specification. In this paper, we consider only objects whose
sequential specifications are total : if the object has a pending invocation,
may also include argument values.
then it has a matching enabled response. For example, a partial deq might
be undefined when applied to an empty queue, while a total deq would return
an exception. We restrict out attention to objects whose operations
are total because it is unclear how to interpret the wait-free condition for
partial operations. For example, the most natural way to define the effects
of a partial deq in a concurrent system is to have it wait until the queue
becomes non-empty, a specification that clearly does not admit a wait-free
implementation.
Each history H induces a partial "real-time" order OE H on its opera-
tions: op 0 OE H op 1 if the response for op 0 precedes the invocation for op 1 .
Operations unrelated by OE H are said to be concurrent. If H is sequential,
OE H is a total order. Let complete(H) denote the maximal subsequence of H
consisting only of invocations and matching responses. A concurrent system
is linearizable if, for each history H , there exists a
sequential history S such that:
ffl For all
In other words, the history "appears" sequential to each individual process,
and this apparent sequential interleaving respects the real-time precedence
ordering of operations. Equivalently, each operation appears to take effect
instantaneously at some point between its invocation and its response. A
concurrent object A is linearizable [14] if, for every history H of every concurrent
system linearizable. A
linearizable object is thus "equivalent" to a sequential object, and its operations
can also be specified by simple pre- and postconditions. Henceforth, all
objects are assumed to be linearizable. Unlike related correctness conditions
such as sequential consistency [17] or strict serializability [24], linearizability
is a local property: a concurrent system is linearizable if and only if each individual
object is linearizable [14]. We restrict our attention to linearizable
concurrent systems.
2.3 Implementations
An implementation of an object A is a concurrent system fF
where the F i are called front-ends, and R is called the representation object.
Informally, R is the data structure that implements A, and F i is the procedure
called by process P i to execute an operation. An object implementation
is shown schematically in Figure 2.
OE
Process
invoke
oe respond
OE
Front-End
invoke
oe respond
OE
Object R
Object A

Figure

2: Schematic View of Object Implementation
ffl The external events of the implementation are just the external events
of A: each input event of A is an input event of F i ,
and each output event of A is an output event of
ffl The implementation has the following internal events: each input event
of R is composed with the matching output event
of F i , and each output event res; R) of R is composed
with the matching input event of F i .
ffl To rule out certain trivial solutions, front-ends share no events; they
communicate indirectly through R.
Let I j be an implementation of A j . I j is correct, if for every history
H of every system fP there exists a history
H 0 of fP g, such that HjfP
g.
An implementation is wait-free if:
ffl It has no history in which an invocation of P i remains pending across
an infinite number of steps of F i .
ffl If P i has a pending invocation in a state s, then there exists a history
fragment starting from s, consisting entirely of events of F i and R,
that includes the response to that invocation.
The first condition rules out unbounded busy-waiting: a front-end cannot
take an infinite number of steps without responding to an invocation.
The second condition rules out conditional waiting: F i cannot block waiting
for another process to make a condition true. Note that we have not found
it necessary to make fairness or liveness assumptions: a wait-free implementation
guarantees only that that if R eventually responds to all invocations
of F i , then F i will eventually respond to all invocations of P i , independently
of process speeds.
An implementation is bounded wait-free if there exists N such that there
is no history in which an invocation of P i remains pending across N steps of
F i . Bounded wait-free implies wait-free, but not vice-versa. We use the wait-free
condition for impossibility results, and the bounded wait-free condition
for universal constructions.
For brevity, we say that R implements A if there exists a wait-free implementation
of A. It is immediate from the definitions that
implements is a reflexive partial order on the universe of objects. In the rest
of the paper, we investigate the mathematical structure of the implements
relation. In the next section, we introduce a simple technique for proving
that one object does not implement another, and in the following section we
display some "universal" objects capable of implementing any other object.
3 Impossibility Results
Informally, a consensus protocol is a system of n processes that communicate
through a set of shared objects fX g. The processes each start with
an input value from some domain D, they communicate with one another
by applying operations to the shared objects, they eventually agree on a
common input value and halt. A consensus protocol is required to be:
ffl Consistent: distinct processes never decide on distinct values.
ffl Wait-free: each process decides after a finite number of steps.
ffl Valid: the common decision value is the input to some process.
For our purposes, it is convenient to express the consensus problem using
the terminology of abstract data types. A consensus object provides a single
operation:
decide(input: value) returns(value)
A protocol's sequential specification is simple: all decide operations return
the argument value of the first decide (c.f., Plotkin's ``sticky-bit'' [27]).
This common value is called the history's decision value. A wait-free linearizable
implementation of a consensus object is called a consensus protocol
(c.f., Fisher, Lynch, and Paterson [9]).
We will investigate the circumstances under which it is possible to construct
consensus protocols from particular objects. Most of the constructions
presented in this paper use multi-reader/multi-writer registers in addition
to the object of interest. For brevity we say "X solves n-process consensus"
if there exists a consensus protocol fF is a set of
read/write registers, and W and X may be initialized to any state.
1 The consensus number for X is the largest n for which X
solves n-process consensus. If no largest n exists, the consensus number is
said to be infinite.
It is an immediate consequence of our definitions that if Y implements X ,
and X solves n-process consensus, then Y also solves n-process consensus.
Theorem 2 If X has consensus number n, and Y has consensus number
exists no wait-free implementation of X by Y in a system
of more than m processes.
Proof: As noted above, all front-end and object automata are compatible by
definition, and thus their composition is well-defined. Let fF
be a consensus protocol, where k ? m and W is a set of read/write regis-
ters. Let fF 0
be an implementation of X . It is easily checked
that
is wait-free, and because composition
is associative, it is identical to fF 1
1 is
the composition of F i and F 0
. Since the former is a consensus protocol, so
is the latter, contradicting the hypothesis that Y has consensus number m.
In the rest of this section, we consider a number of objects, displaying
consensus protocols for some, and impossibility results for others. For impossibility
proofs, we will usually assume the existence of a consensus protocol,
and then derive a contradiction by constructing a sequential execution that
forces the protocol to run forever. When constructing a consensus protocol
for a particular linearizable object, we observe that the linearizability condition
implies that if there exists an execution in which consensus fails, either
because it is inconsistent, invalid, or it runs forever, then there exists an
s
\Gamma\Psi
reads
@
@
@
@
@R
runs alone
decides y
@
@
@
@
@R
decides x
runs alone

Figure

3: P reads first.
s
\Gamma\Psi
x-valent state
@
@
@
@
@R
y-valent state
\Gamma\Psi
@
@
@
@
@R

Figure

4: P and Q write different registers.
equivalent sequential execution with the same property. As a consequence,
a consensus protocol is correct if and only if all its sequential executions are
correct. For brevity, protocols are defined informally by pseudo-code; their
translations into I/O automata should be self-evident.
3.1 Atomic Read/Write Registers
In this section, we show there exists no two-process consensus protocol
using multi-reader/multi-writer atomic registers. First, some terminology.
A protocol state is bivalent if either decision value is still possible: i.e.,
the current execution can be extended to yield different decision values.
Otherwise it is univalent. An x-valent state is a univalent state with eventual
decision value x. A decision step is an operation that carries a protocol from
a bivalent to a univalent state.
Theorem 3 Read/write registers have consensus number 1.
s
\Gamma\Psi
@
@
@
@
@R
\Gamma\Psi
\Gamma\Psi
decides x
runs alone
\Gamma\Psi
decides y
runs alone

Figure

5: P and Q write the same register.
Proof: Assume there exists a two-process consensus protocol implemented
from atomic read/write registers. We derive a contradiction by constructing
an infinite sequential execution that keeps any such protocol in a bivalent
state. If the processes have different input values, the validity condition
implies that the initial state is bivalent. Consider the following sequential
execution, starting from the initial state. In the first stage, P executes a
sequence of operations (i.e., alternates matching invocation and response
events) until it reaches a state where the next operation will leave the protocol
in a univalent state. P must eventually reach such a state, since it
cannot run forever, and it cannot block. In the second stage, Q executes
a sequence of operations until it reaches a similar state, and in successive
stages, P and Q alternate sequences of operations until each is about to make
a decision step. Because the protocol cannot run forever, it must eventually
reach a bivalent state s in which any subsequent operation of either process
is a decision step. Suppose P 's operation carries the protocol to an x-valent
state, and Q's operation carries the protocol to a y-valent state, where x
and y are distinct.
ffl Suppose the decision step for one process, say P , is to read a shared
register (Figure 3). Let s 0 be the protocol state immediately following
the read. The protocol has a history fragment starting from s, con-
RMW(r: register, f: function) returns(value)
previous := r
r := f(r)
return previous

Figure

sisting entirely of operations of Q, yielding decision value y. Since the
states s and s 0 differ only in the internal state of P , the protocol has
the same history fragment starting in s 0 , an impossibility because s 0 is
x-valent.
ffl Suppose the processes write to different registers (Figure 4). The state
that results if P 's write is immediately followed by Q's is identical to
the state that results if the writes occur in the opposite order, which
is impossible, since one state is x-valent and the other is y-valent.
ffl Suppose the processes write to the same register (Figure 5). Let s 0 be
the x-valent state immediately after P 's write. There exists a history
fragment starting from s 0 consisting entirely of operations of P that
yields the decision value x. Let s 00 be the y-valent state reached if Q's
write is immediately followed by P 's. Because P overwrites the value
written by Q, s 0 and s 00 differ only in the internal states of Q, and
therefore the protocol has the same history fragment starting from s 00 ,
an impossibility since s 00 is y-valent.
Similar results have been shown by Loui and Abu-Amara [21], Chor,
Israeli, and Li [6], and Anderson and Gouda [1]. Our contribution lies in
the following corollary:
Corollary 4 It is impossible to construct a wait-free implementation of any
object with consensus number greater than 1 using atomic read/write registers

3.2 Read-Modify-Write Operations
decide(input: value) returns(value)
prefer[P] := input
then return prefer[P]
else return prefer[Q]
decide

Figure

7: Read-Modify-Write: Two-Process Consensus
Kruskal, Rudolph, and Snir [15] have observed that many, if not all,
of the classical synchronization primitives can be expressed as read-modify-
write operations, defined as follows. Let r be a register, and f a function
from values to values. The operation RMW(r; f) is informally defined by the
procedure shown in Figure 6, which is executed atomically. If f is the iden-
tity, RMW(r; f) is simply a read operation. A read-modify-write operation
is non-trivial if f is not the identity function. Examples of well-known non-trivial
read-modify-write operations include test&set, swap, compare&swap,
and fetch&add. Numerous others are given in [15].
Theorem 5 A register with any non-trivial read-modify-write operation has
a consensus number at least 2.
Proof: Since f is not the identity, there exists a value v such that v 6= f(v).
Let P and Q be two processes that share a two-register array prefer, where
each entry is initialized to ?, and a read-modify-write register r, initialized
to v. P executes the protocol shown in Figure 7 (Q's protocol is symmetric.)
Expressed in terms of the I/O automaton model, the read-modify-write
register r is the object X , the prefer array is the set of atomic registers
W , and the pseudo-code in Figure 7 defines the front-end automaton for
. The front-end has three output events: the write and RMW invocations
sent to r and prefer, and the decision value returned to P . Similarly, its
input events are P 's invocation of decide, and the responses to the write and
RMW invocations.
As noted above, because r and prefer are linearizable, it suffices to check
correctness for sequential executions. The only operations that do not commute
are the two read-modify-write operations applied to r. The protocol
chooses P 's input if P 's operation occurs first, and Q's input otherwise.
Corollary 6 It is impossible to construct a wait-free implementation of any
non-trivial read-modify-write operation from a set of atomic read/write registers
in a system with two or more processes.
Although read-modify-write registers are more powerful than read/write
registers, many common read-modify-write operations are still computationally
weak. In particular, one cannot construct a wait-free solution to
three process consensus using registers that support any combination of read,
write, test&set, swap, and fetch&add operations. Let F be a set of functions
indexed by an arbitrary set S. Define F to be interfering if for all values v
and all i and j in S, either (1) f i and f j commute: f i (f j
or (2) one function "overwrites" the other: either f i (f j
Theorem 7 There is no wait-free solution to three-process consensus using
any combination of read-modify-write operations that apply functions from
an interfering set F .
Proof: By contradiction. Let the three processes be P , Q, and R. As
in the proof of Theorem 2, we construct a sequential execution leaving the
protocol in bivalent state where every operation enabled for P and Q is a
decision step, some operation of P carries the protocol to an x-valent state,
and some operation of Q carries the protocol to a y-valent state, where x
and y are distinct. By the usual commutativity argument, P and Q must
operate on the same register; say, P executes
Let v be the current value of register r. There are two cases to consider.
First, suppose f i (f j (v)). The state s that results if P executes
x-valent, thus there exists some
history fragment consisting entirely of operations of R that yields decision
value x. Let s 0 be the state that results if P and Q execute their operations
in the reverse order. Since the register values are identical in s and s 0 ,
the protocol has the same history fragment starting in s 0 , contradicting the
hypothesis that s 0 is y-valent.
Second, suppose f i (f j (v). The state s that results if P executes
x-valent, thus there exists some
history fragment consisting entirely of operations of R that yields decision
value x. Let s 0 be the state that results if Q alone executes its operation.
Since the register values are identical in s and s 0 , the protocol has the same
compare&swap(r: register, old: value, new: value)
returns(value)
previous := r
if previous = old
then r := new
return previous

Figure

8: Compare&Swap
history fragment starting in s 0 , contradicting the hypothesis that s 0 is y-
valent.
It follows that one cannot use any combination of these classical primitives
to construct a wait-free implementation of any object with consensus
number greater than 2.
Another classical primitive is compare&swap, shown in Figure 8. This
primitive takes two values: old and new. If the register's current value is
equal to old , it is replaced by new , otherwise is left unchanged. The register's
old value is returned.
Theorem 8 A compare&swap register has infinite consensus number.
Proof: In the protocol shown in Figure 9, the processes share a register
r initialized to ?. Each process attempts to replace ? with its input; the
decision value is established by the process that succeeds.
This protocol is clearly wait-free, since it contains no loops. Consistency
follows from the following observations: (1) r 6= ? is a postcondition of
compare&swap, and (2) for any v 6= ?, the assertion r = v is stable - once
it becomes true, it remains true. Validity follows from the observation that
if r 6= ?, then r contains some process's input.
Corollary 9 It is impossible to construct a wait-free implementation of a
compare&swap register from a set of registers that support any combination
of read, write, test&set, swap, or fetch&add operations in a system of three
or more processes.
decide(input: value) returns(value)
first := compare&swap(r, ?, input)
then return input
else return first
decide

Figure

9: Compare&Swap: n-Process Consensus
decide(input: value) returns(value)
prefer[P] := input
then return prefer[P]
else return prefer[Q]
decide

Figure

10: FIFO Queues: Two-Process Consensus
3.3 Queues, Stacks, Lists, Etc.
Consider a FIFO queue with two operations: enq places an item at the
end of the queue, and deq removes the item from the head of the queue,
returning an error value if the queue is empty.
Theorem 10 The FIFO queue has consensus number at least 2.
Proof:

Figure

shows a two-process consensus protocol. The queue is
initialized by enqueuing the value 0 followed by the value 1. As above, the
processes share a two-element array prefer. P executes the protocol shown
in

Figure

(Q's protocol is symmetric). Each process dequeues an item
from the queue, returning its own preference if it dequeues 0, and the other's
preference if it dequeues 1.
The protocol is wait-free, since it contains no loops. If each process
returns its own input, then they must both have dequeued 0, violating the
queue specification. If each returns the others' input, then they must both
have dequeued 1, also violating the queue specification. Let the "winner" be
the process that dequeues 0. Validity follows by observing that the winner's
position in prefer is initialized before the first queue operation.
Trivial variations of this program yield protocols for stacks, priority
queues, lists, sets, or any object with operations that return different results
if applied in different orders.
Corollary 11 It is impossible to construct a wait-free implementation of
a queue, stack, priority queue, set, or list from a set of atomic read/write
registers.
Although FIFO queues solve two-process consensus, they cannot solve
three-process consensus.
Theorem 12 FIFO queues have consensus number 2.
Proof: By contradiction. Assume we have a consensus protocol for processes
As before, we maneuver the protocol to a state where
P and Q are each about to make a decision step. Assume that P 's operation
would carry the protocol to an x-valent state and Q's to a y-valent state.
The rest is a case analysis.
First, suppose P and Q both execute deq operations. Let s be the protocol
state if P dequeues and then Q dequeues, and let s 0 be the state if
the dequeues occur in the opposite order. Since s is x-valent, there exists
a history fragment from s, consisting entirely of operations of R, yielding
decision value x. But s and s 0 differ only in the internal states of P and
Q, thus the protocol has the same history fragment from s 0 , a contradiction
because s 0 is y-valent.
suppose P does an enq and Q a deq. If the queue is non-empty,
the contradiction is immediate because the two operations commute: R cannot
observe the order in which they occurred. If the queue is empty, then
the y-valent state reached if Q dequeues and then P enqueues is indistinguishable
to R from the x-valent state reached if P alone enqueues.
Finally, suppose both P and Q do enq operations. Let s be the state at
the end of the following execution:
1. P and Q enqueue items p and q in that order.
2. Run P until it dequeues p. (Since the only way to observe the queue's
state is via the deq operation, P cannot decide before it observes one
of p or q.)
3. Run Q until it dequeues q.
Let s 0 be the state after the following alternative execution:
decide(input: value) returns(value)
enq(q, input)
return peek(q)
decide

Figure

Augmented FIFO Queue: n-Process Consensus
1. Q and P enqueue items q and p in that order.
2. Run P until it dequeues q.
3. Run Q until it dequeues p.
Clearly, s is x-valent and s 0 is y-valent. Both of P 's executions are identical
until it dequeues p or q. Since P is halted before it can modify any other
objects, Q's executions are also identical until it dequeues p or q. By a
now-familiar argument, a contradiction arises because s and s 0 are indistinguishable
to R.
Trivial variations of this argument can be applied to show that many
similar data types, such as sets, stacks, double-ended queues, and priority
queues, all have consensus number 2.
A message-passing architecture (e.g., a hypercube, [28]) is a set of processors
that communicate via shared FIFO queues. Theorem 12 implies that
message-passing architectures cannot solve three-process consensus or implement
any object that can. Dolev, Dwork, and Stockmeyer [7] give a related
result: point-to-point FIFO message channels cannot solve two-process con-
sensus. That result does not imply Theorem 12, however, because a queue
item, unlike a message, is not "addressed" to any particular process, and
hence it can be dequeued by anyone.
3.4 An Augmented Queue
Let us augment the queue with one more operation: peek returns but
does not remove the first item in the queue.
Theorem 13 The augmented queue has infinite consensus number.
Proof: In the protocol shown in Figure 11, the queue q is initialized to
empty, and each process enqueues its own input. The decision value is the
input of the process whose enq occurs first.
decide(input: value) returns(value)
prefer[P] := input 1
for i in P+1 . n do 3
r[i,
for i in n . 1 do 6
then return prefer[i] 8
decide

Figure

12: Memory-To-Memory Move: n-Process Consensus
As usual, the protocol is wait-free, since it contains no loops. Consistency
follows from the following observations: (1) "the queue is non-empty" is a
postcondition of each enq, and hence a precondition for each peek, and (2)
for any v, "v is the first item in the queue" is stable. Validity follows from
the observation that the first item in the queue is some process's input.
Corollary 14 It is impossible to construct a wait-free implementation of
the augmented queue from a set of registers supporting any combination of
read, write, test&set, swap, or fetch&add operations.
Corollary 15 It is impossible to construct a wait-free implementation of
the augmented queue from a set of regular queues.
The fetch&cons operation atomically threads an item onto the front of a
linked list. By an argument virtually identical to the one given for Theorem
13, a linked list with fetch&cons has infinite consensus number.
3.5 Memory-To-Memory Operations
Consider a collection of atomic read/write registers having one additional
operation: move atomically copies the value of one register to another 3 . We
use the expression "a / b" to move the contents of b to a.
3 Memory-to-memory move should not be confused with assignment; the former copies
values between two public registers, while the latter copies values between public and
private registers.
Theorem An array of registers with move has infinite consensus number

Proof: An n-process consensus protocol appears in Figure 12. The processes
share two arrays: prefer[1::n] and r[1::n; 1::2], where r[P; 1] is initialized
to 1 and r[P; 2] to 0, for n. The protocol is clearly wait-free,
since all loops are bounded.
To show consistency, we use the following assertions:
It is easily checked that P(P ), Q(P ), and S(P ) are stable for each P , that
P(P ) and Q(P ) are mutually exclusive, that S(P ) is true after P executes
Statement #2, and that S(i) is true after each execution of Statement #4.
We say that a process P has stabilized if S(P ) holds.
We claim that if P(P ) holds for some P , then Q(Q) holds for some
and that every process between Q and P has stabilized. Let P be the
least process for which P(P ) holds. Since r[P; 1] and r[P; 2] are both 0, some
must have assigned 0 to r[P; 1] (Statement #4) before P executed
Statement #2. Q, however, executes Statement #2 before Statement #4,
hence S(Q) holds. Since P(Q) is false by hypothesis, Q(Q) must hold.
Moreover, if Q has assigned to r[P; 1], then it has assigned to every r[P
for thus each such P 0 has stabilized.
Define the termination assertion as follows:
T is stable, and it holds for at most one process. When P finishes the
first loop (Statements #3-5), every process greater than or equal to P has
stabilized. If any of them satisfies T , we are done. Otherwise, there exists
a largest all the processes between P and Q
have stabilized, implying that T (Q) holds. When P 's protocol terminates,
it chooses the input of the unique Q satisfying T (Q). Since the termination
assertion is stable, all processes agree.
Validity follows because prefer[P ] must be initialized before T (P ) can
become true.
decide(input: value) returns(value)
prefer[P] := input
for Q in 1 . n do
then return prefer[Q]
end for
decide

Figure

13: Memory-To-Memory Swap: n-Process Consensus
Theorem 17 An array of registers with memory-to-memory swap 4 has
infinite consensus number.
Proof: The protocol is shown in Figure 13. The processes share an array
of registers a[1::n] whose elements are initialized to 0, and a single register
r, initialized to 1. The first process to swap 1 into a wins. The protocol
is wait-free because the loop is bounded. To show consistency, consider the
following assertions, where "9!P " means "there exists a unique P ."
The first assertion is invariant, and the second is stable and becomes true
after the first swap. It follows that each process observes a unique, stable P
such that a[P
Validity follows because each process initializes its position in prefer
before executing a swap.
Corollary It is impossible to construct a wait-free implementation of
memory-to-memory move or swap from a set of registers that support any
combination of read, write, test&set, swap, or fetch&add operations.
Corollary 19 It is impossible to construct a wait-free implementation of
memory-to-memory move or swap from a set of FIFO queues.
4 The memory-to-memory swap should not be confused with the read-modify-write
swap; the former exchanges the values of two public registers, while the latter exchanges
the value of a public register with a processor's private register.
3.6 Multiple Assignment
The expression:
atomically assigns each value v i to each register r i .
Theorem 20 Atomic m-register assignment has consensus number at least
m.
Proof: The protocol uses m "single-writer" registers r
writes to register r i , and m(m\Gamma1)=2 "multi-writer" registers r ij , where i ? j,
both write to register r ij . All registers are initialized to
?. Each process atomically assigns its input value to m registers: its single-writer
register and its registers. The decision value of
the protocol is the first value to be assigned.
After assigning to its registers, a process determines the relative ordering
of the assignments for two processes P i and P j as follows.
. If the value is ?, then neither assignment has occurred.
ffl Otherwise, read r i and r j . If r i 's value is is ?, then P j precedes P i ,
and similarly for r j .
ffl If neither r i nor r j is ?, reread r ij . If its value is equal to the value
read from r i , then P j precedes P i , else vice-versa.
By repeating this procedure, a process can determine the value written
by the earliest assignment.
This result can be improved.
Theorem 21 Atomic m-register assignment has consensus number at least
2.
Proof: Consider the following two-phase protocol. Each process has two
single-writer registers, one for each phase, and each pair of processes share
a register. Divide the processes into two predefined groups of m \Gamma 1. In the
first phase, each group achieves consensus within itself using the protocol
from Theorem 20. In the second phase, each process atomically assigns
its group's value to its phase-two single-writer register and the
registers shared with processes in the other group. Using the ordering
procedure described above, the process constructs a directed graph G with
the property that there is an edge from P j to P k if P j and P k are in different
groups and the former's assignment precedes the latter's. It then locates
a source process having at least one outgoing edge but no incoming edges,
and returns that process's value. At least one process has performed an
assignment, thus G has edges. Let Q be the process whose assignment is
first in the linearization order. Q is a source, and it has an outgoing edge to
every process in the other group, thus no process in the other group is also
a source. Therefore, all source processes belong to the same group.
This algorithm is optimal with respect to the number of processes.
Theorem 22 Atomic m-register assignment has consensus number exactly
2.
Proof: We show that atomic m-register assignment cannot solve 2m \Gamma 1-
process consensus for m ? 1. By the usual construction, we can maneuver
the protocol into a bivalent state s in which any subsequent operation executed
by any process is a decision step. We refer to the decision value forced
by each process as its default.
We first show that each process must have a "single-writer" register that
it alone writes to. Suppose not. Let P and Q be processes with distinct
defaults x and y. Let s 0 be the state reached from s if P performs its
assignment, Q performs its assignment, and the other processes perform
theirs. Because P went first, s 0 is x-valent. By hypothesis, every register
written by P has been overwritten by another process. Let s 00 be the state
reached from s if P halts without writing, but all other processes execute in
the same order. Because Q wrote first, s 00 is y-valent. There exists a history
fragment from s 0 , consisting entirely of operations of Q, with decision value
x. Because the values of the registers are identical in s 0 and s 00 , the protocol
has the same history fragment from s 00 , a contradiction because s 00 is y-valent.
We next show that if P and Q have distinct default values, then there
must be some register written only by those two processes. Suppose not.
Let s 0 be the state reached from s if P performs its assignment, Q performs
its assignment, followed by all other processes' assignments. Let s 00 be the
state reached by the same sequence of operations, except that P and Q
execute their assignments in the reverse order. Because s 0 is x-valent, there
exists a history fragment from s 0 consisting of operations of P that with
decision value x. But because every register written by both P and Q has
been overwritten by some other process, the register values are the same in
both s and s 0 , hence the protocol has the same history fragment from s 00 , a
contradiction.
It follows that if P has default value x, and there are k processes with
different default values, then P must assign to k registers. If there are
which do not all have the same default, then some process
must disagree with at least m other processes, and that process must must
assign to m+ 1 registers.
The last theorem shows that consensus is irreducible in the following
sense: it is impossible to achieve consensus among 2n processes by combining
protocols that achieve consensus among at most 2m ! 2n processes. If
it were possible, one could implement each individual 2m-process protocol
using yielding a 2n-process consensus protocol,
contradicting Theorem 22.
3.7 Remarks
Fischer, Lynch, and Paterson [9] have shown that there exists no two-process
consensus protocol using message channels that permit messages to be delayed
and reordered. That result does not imply Theorem 3, however, because
atomic read/write registers lack certain commutativity properties of
asynchronous message buffers. (In particular, Lemma 1 of [9] does not hold.)
Dolev, Dwork, and Stockmeyer [7] give a thorough analysis of the circumstances
under which consensus can be achieved by message-passing. They
consider the effects of thirty-two combinations of parameters: synchronous
vs. asynchronous processors, synchronous vs. asynchronous communication,
FIFO vs. non-FIFO message delivery, broadcast vs. point-to-point transmis-
sion, and whether send and receive are distinct primitives. Expressed in their
terminology, our model has asynchronous processes, synchronous communi-
cation, and distinct send and receive primitives. We model send and receive
as operations on a shared message channel object; whether delivery is FIFO
and whether broadcast is supported depends on the type of the channel.
Some of their results translate directly into our model: it is impossible to
achieve two-process consensus by communicating through a shared channel
that supports either broadcast with unordered delivery, or point-to-point
transmission with FIFO delivery. Broadcast with ordered delivery, however,
does solve n-process consensus.
A safe read/write register [19] is one that behaves like an atomic read/write
register as long as operations do not overlap. If a read overlaps a write,
however, no guarantees are made about the value read. Since atomic registers
implement safe registers, safe registers cannot solve two-process con-
sensus, and hence the impossibility results we derive for atomic registers
apply equally to safe registers. Similar remarks apply to atomic registers
that restrict the number of readers or writers.
Loui and Abu-Amara [21] give a number of constructions and impossibility
results for consensus protocols using shared read-modify-write registers,
which they call "test&set" registers. Among other results, they show that
n-process consensus for n ? 2 cannot be solved by read-modify-write operations
on single-bit registers.
Lamport [18] gives a queue implementation that permits one enqueuing
process to execute concurrently with one dequeuing process. With minor
changes, this implementation can be transformed into a wait-free implementation
using atomic read/write registers. Theorem 3 implies that Lamport's
queue cannot be extended to permit concurrent deq operations without augmenting
the read and write operations with more powerful primitives.
A concurrent object implementation is non-blocking if it guarantees that
some process will complete an operation in a finite number of steps, regardless
of the relative execution speeds of the processes. The non-blocking
condition guarantees that the system as a whole will make progress despite
individual halting failures or delays. A wait-free implementation is necessarily
non-blocking, but not vice-versa, since a non-blocking implementation
may permit individual processes to starve. The impossibility and universality
results presented in this paper hold for non-blocking implementations as
well as wait-free implementations.
Elsewhere [14], we give a non-blocking implementation of a FIFO queue,
using read, fetch&add, and swap operations, that permits an arbitrary number
of concurrent enq and deq operations. Corollary 14 implies that this
queue implementation cannot be extended to support a non-blocking peek
operation without introducing more powerful primitives.
4 Universality Results
An object is universal if it implements any other object. In this section,
we show that any object with consensus number n is universal in a system
of n (or fewer) processes. The basic idea is the following: we represent the
object as a linked list, where the sequence of cells represents the sequence of
operations applied to the object (and hence the object's sequence of states).
A process executes an operation by threading a new cell on to the end of the
list. When the cell becomes sufficiently old, it is reclaimed and reused. Our
construction requires O(n 3 ) memory cells to represent the object, and O(n 3 )
worst-case time to execute each operation. We assume cells can hold integers
of unbounded size. Our presentation is intended to emphasize simplicity, and
omits many obvious optimizations.
Let invoc be the object's domain of invocations, result its domain
of results, and state its domain of states. An object's behavior may be
specified by the following relation:
apply ae invoc \Theta state \Theta state \Theta result.
This specification means that applying operation p in state s leaves the
object in a state s 0 and returns result value r, where hp; s; s ri 2 apply .
Apply is a relation (rather than a function) because the operation may be
non-deterministic. For brevity, we use the notation apply(p; s) to denote an
arbitrary pair hs ri such that hp; s; s ri 2 apply .
4.1 The Algorithm
An object is represented by a doubly-linked list of cells having the following
fields:
ffl Seq is the cell's sequence number in the list. This field is zero if the
cell is initialized but not yet threaded onto the list, and otherwise it is
positive. Sequence numbers for successive cells in the list increase by
one.
ffl Inv is the invocation (operation name and argument values).
ffl New is a consensus object whose value is the pair hnew.state, new.resulti.
The first component is the object's state following the operation, and
the second is the operation's result value, if any.
ffl Before is a pointer to the previous cell in the list. This field is used
only for free storage management.
ffl After is consensus object whose value is a pointer to the next cell in
the list.
If c and d are cells, the function max(c; d) returns the cell with the higher
sequence number.
Initially, the object is represented by a unique anchor cell with sequence
number 1, holding a creation operation and an initial state.
The processes share the following data structures.
ffl Announce is an n-element array whose P th element is a pointer to the
cell P is currently trying to thread onto the list. Initially all elements
point to the anchor cell.
ffl Head is an n-element array whose P th element is a pointer to the last
cell in the list that P has observed. Initially all elements point to the
anchor cell.
Let max(head) be max(head
denote the assertion that a pointer to cell c has been assigned to head [Q],
for some Q.
We use the following auxiliary variables:
is the set of cells whose addresses have been stored in the
head array since P 's last announcement.
start(P ) is the the value of max(head) at P 's last announcement.
Notice that:
Auxiliary variables do not affect the protocol's control flow; they are present
only to facilitate proofs.
The protocol for process P is shown in Figure 14. In this figure, "v:
declares and initializes variable v of type T to a value e, and the
type "*cell" means "pointer to cell." Sequences of statements enclosed in
angle brackets are executed atomically. In each of these compound state-
ments, only the first affects shared data or control flow; the remainder are
"bookkeeping operations" that update auxiliary variables. For readability,
auxiliary variables are shown in italics.
Informally, the protocol works as follows. P allocates and initializes a
cell to represent the operation (Statement #1). It stores a pointer to the cell
in announce[P ] (Statement #2), ensuring that if P itself does not succeed in
threading its cell onto the list, some other process will. To locate a cell near
the end of the list, P scans the head array, setting head [P ] to the cell with
the maximal sequence number (Statement #3). P then enters the main loop
of the protocol (Statement #4), which it executes until its own cell has been
threaded onto the list (detected when its sequence number becomes non-
zero). P chooses a process to "help" (Statement #6), and checks whether
that process has an unthreaded cell (Statement #7). If so, then P will try
to thread it, otherwise it tries to thread its own cell. (If this helping step
were omitted, the protocol would be non-blocking rather than wait-free.) P
tries to set head [P ].after to point to the cell it is trying to thread (Statement
#8). The after field must be a consensus cell to ensure that only one process
succeeds in setting it. Whether or not P succeeds, it then initializes the
remaining fields of the next cell in the list. Because the operation may be
non-deterministic, different processes may try to set the new field to different
values, so this field must be a consensus object (Statement #9). The values
of the other fields are computed deterministically, so they can simply be
written as atomic registers (Statements #10 and #11). For brevity, we say
that a process threads a cell in Statement #7 if the decide operation alters
the value of the after field, and it announces a cell at Statement #2 when
it stores the cell's address in announce.
Lemma 23 The following assertion is invariant:
Proof: If jconcur(P )j ? n, then concur(P ) includes successive cells q and
r with respective sequence numbers equal to
threaded by processes Q and R. Because q is in concur(P ), Q threads q
after P 's announcement. Because R cannot modify an unthreaded cell, R
reads announce[P ] (Statement #5) after Q threads q. It follows that R reads
announce[P after P 's announcement, and therefore either announce[P ] is
already threaded, or r is p.
Lemma 23 places a bound on the number of cells that can be threaded
while an operation is in progress. We now give a sequence of lemmas showing
that when P finishes scanning the head array, either announce[P ] is
threaded, or head [P ] lies within cells of the end of the list.
Lemma 24 The following assertion is invariant:
Proof: The sequence number for each head [Q] is non-decreasing.
universal(what: invoc) returns(result)
mine: cell := [seq: 0, 1
inv: what,
new: create(consensus object),
before: create(consensus object)
after: null]
for each process Q do 3
end for
while announce[P
c: *cell := head[P
help: *cell := announce[(c.seq mod n)
then prefer := help
else prefer := announce[P
d := decide(c.after, prefer) 8
decide(d.new, apply(d.inv, c.new.state)) 9
d.before
hhead[P
while
hhead[P
return (announce[P ].new.result) 14
universal

Figure

14: A Universal Construction
Lemma 25 The following is a loop invariant for Statement #3:
max(head [P ];
where Q is the loop index.
Proof: When Q is 1, the assertion is implied by Lemma 24. The truth
of the assertion is preserved at each iteration, when head [P ] is replaced by
max(head [P ]; head [Q]).
Lemma 26 The following assertion holds just before Statement #4:
head [P ]:seq - start(P
Proof: After the loop at Statement #3, max(head [P ]; head
is just head [P ].seq, and the result follows from Lemma 25.
Lemma 27 The following is invariant:
Proof: The lower bound follows from Lemma 26, and the upper bound
follows from Equation 1.
Theorem 28 The protocol in Figure 14 is correct and bounded wait-free.
Proof: Linearizability is immediate, since the order in which cells are
threaded is clearly compatible with the natural partial order of the corresponding
operations.
The protocol is bounded wait-free because P can execute the main loop
no more than times. At each iteration, head [P ].seq increases by one.
implies that
Lemma 23 implies that announce[P ] must be threaded.
4.2 Memory Management
In this section we discuss how cells are allocated and reclaimed. To reclaim
a cell, we assume each consensus object provides a reset operation that
restores the object to a state where it can be reused for a new round of
consensus. Our construction resets a consensus object only when there are
no concurrent operations in progress.
The basic idea is the following: a process executing an operation will
traverse no more than its cell is threaded (Theorem 28).
Conversely, each cell will be traversed no more than times. When a
process is finished threading its cell, it releases each of the preceding
cells by setting a bit. When a cell has been released
to recycle it. Each cell holds an additional field, an array released of n
bits, initially all false. When a process completes an operation, it scans the
setting released[i] to true in the cell at distance i.
Each process maintains a private pool of cells. When a process needs
to allocate a new cell, it scans its pool, and reinitializes the first cell whose
released bits are all true. We assume here that each object has its own
pool; in particular, the cell's new sequence number exceeds its old sequence
number. While a process P is allocating a new cell, the list representing an
object includes at most n \Gamma 1 incomplete operations, and each such cell can
inhibit the reclamation of at most n cells. To ensure that P will find a
needs a pool of at least n 2 cells. Note that locating a free cell
requires at worst O(n 3 ) read operations, since the process may have to scan
cells, and each cell requires reading bits. If an atomic fetch&add
operation is available, then a counter can be used instead of the released
bits, and a free cell can be located in O(n 2 ) read operations.
The proof of Lemma 23 remains unchanged. For Lemma 24, we observe
that a cell can be reclaimed only if it is followed in the list by at least n+ 1
other cells, hence reclaiming a cell cannot affect the value of max(head).
The statement of Lemma 26 needs to be strengthened:
Lemma 29 The following assertion holds just before Statement #4:
Proof: When P announces its cell, there is some process Q such that
head [Q] has sequence number greater than or equal to start(P ). This cell
can be reclaimed only if n+1 other cells are threaded in front of it, implying
that jconcur(P )j - n+ 1, and hence that announce[P
The proof of Theorem 28 proceeds as before. There is one last detail to
check: if P 's cell has not been threaded by the time it finishes scanning head ,
then we claim that none of the cells it traverses will be reclaimed while the
operation is in progress. Lemma 23 states that the list cannot have grown
by more than n cells since P 's announcement, thus every cell reachable from
lies within n+1 cells of the end of the list, or of announce[P ] if it is
threaded. In either case, those cells cannot be reclaimed while P 's operation
is in progress, since they must have at least one released bit unset.
4.3 Remarks
The first universal construction [12] used unbounded memory. Plotkin [27]
describes a universal construction employing "sticky-byte" registers, a kind
of write-once memory. In Plotkin's construction, cells are allocated from a
common pool, and reclaimed in a way similar to ours. The author [13] describes
a universal construction using compare&swap that is currently being
implemented on a multiprocessor.
A randomized wait-free implementation of a concurrent object is one that
guarantees that any process can complete any operation in a finite expected
number of steps. Elsewhere [2], we give a randomized consensus protocol
using atomic registers whose expected running time is polynomial in the
number of processes. This protocol has several important implications. If
the wait-free guarantee is allowed to be probabilistic in nature, then the
hierarchy shown in Figure 1 collapses because atomic registers become uni-
versal. Moreover, combining the randomized consensus protocol with our
universal construction yields a polynomial-time randomized universal con-
struction. Bar-Noy and Dolev [3] have adapted our randomized consensus
protocol to a message-passing model; that protocol can be used to manage
randomized wait-free replicated data objects.
Conclusions
Wait-free synchronization represents a qualitative break with the traditional
locking-based techniques for implementing concurrent objects. We have
tried to suggest here that the resulting theory has a rich structure, yielding
a number of unexpected results with consequences for algorithm design,
multiprocessor architectures, and real-time systems. Nevertheless, many interesting
problems remain unsolved. Little is known about lower bounds
for universal constructions, both in terms of time (rounds of consensus) and
space (number of cells). The implements relation may have additional structure
not shown in the impossibility hierarchy of Figure 1. For example, can
atomic registers implement any object with consensus number 1 in a system
of two or more processes? Can fetch&add implement any object with
consensus number 2 in a system of three or more processes? Does the implements
relation have a different structure for bounded wait-free, wait-free,
or non-blocking synchronization? Finally, little is known about practical
implementation techniques.

Acknowledgments

I am grateful to Jim Aspnes, Vladimir Lanin, Michael Merritt, Serge Plotkin,
Mark Tuttle, Jennifer Welch, and the anonymous referees for many invaluable
suggestions.



--R

The virtue of patience: Concurrent programming with and without waiting.
Fast randomized consensus using shared memory.
Shared memory vs. message-passing in an asynchronous distributed environment
Constructing two-writer atomic registers
Constructing multi-reader atomic values from non-atomic values
On processor coordination using asynchronous hardware.
On the minimal synchronism needed for distributed consensus.
The ibm research parallel processor prototype (rp3): introduction and architecture.
Impossibility of distributed commit with one faulty process.
The nyu ultracomputer - designing an mimd parallel com- puter
Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors.
Impossibility and universality results for wait-free syn- chronization
A methodology for implementing highly concurrent data structures.
Axioms for concurrent objects.

Concurrent reading and writing.
How to make a multiprocessor computer that correctly executes multiprocess programs.
Specifying concurrent program modules.
On interprocess communication
Concurrent set manipulation without lock- ing
Memory Requirements for Agreement Among Unreliable Asynchronous Processes
An introduction to input/output au- tomata
A protocol for wait-free
The serializability of concurrent database updates.
Concurrent reading while writing.
Concurrent reading while writing ii: the multi-writer case
bits and universality of consensus.
The cosmic cube.
The elusive atomic register revisited.
Database applications of the fetch-and-add instruction
Atomic shared register access by asynchronous hardware.
--TR
The cosmic cube
On the minimal synchronism needed for distributed consensus
Efficient synchronization of multiprocessors with shared memory
Axioms for concurrent objects
On processor coordination using asynchronous hardware
The elusive atomic register revisited
Constructing multi-reader atomic values from non-atomic values
A protocol for wait-free, atomic, multi-reader shared variables
Constructing two-writer atomic registers
Impossibility and universality results for wait-free synchronization
bits and universality of consensus
Shared-memory vs. message-passing in an asynchronous distributed environment
Fast randomized consensus using shared memory
A methodology for implementing highly concurrent data structures
Impossibility of distributed consensus with one faulty process
Concurrent set manipulation without locking
The serializability of concurrent database updates
Concurrent Reading While Writing
Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors
Specifying Concurrent Program Modules
Concurrent reading and writing

--CTR
Ted Herman , Valeriu Damian-Iordache, Space-optimal wait-free queues, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.280, August 21-24, 1997, Santa Barbara, California, United States
Matei David, Brief announcement: a single enqueuer wait-free queue implementation, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
John D. Valois, Space bounds for transactional synchronization, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.243, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Wai-Kau Lo, More on
Martha J. Kosa, Lazy-writer multivalued registers, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.270, August 20-23, 1995, Ottowa, Ontario, Canada
Jason Liu , David M. Nicol , King Tan, Lock-free scheduling of logical processes in parallel simulation, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.22-31, May 15-18, 2001, Lake Arrowhead, California, United States
Philippas Tsigas , Yi Zhang, A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.134-143, July 2001, Crete Island, Greece
Olin Shivers , James W. Clark , Roland McGrath, Atomic heap transactions and fine-grain interrupts, ACM SIGPLAN Notices, v.34 n.9, p.48-59, Sept. 1999
Shenk, The consensus hierarchy is not robust, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.279, August 21-24, 1997, Santa Barbara, California, United States
Robert D. Blumofe , Dionisios Papadopoulos, The performance of work stealing in multiprogrammed environments (extended abstract), ACM SIGMETRICS Performance Evaluation Review, v.26 n.1, p.266-267, June 1998
Martha J. Kosa, Wait-free lazy-writer registers with eager readers, Proceedings of the 36th annual Southeast regional conference, p.274-276, April 1998
M. P. Herlihy , J. E. B. Moss, Lock-Free Garbage Collection for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.304-311, May 1992
Hadzilacos, A note on group mutual exclusion, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.100-106, August 2001, Newport, Rhode Island, United States
James H. Anderson , Mark Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.184-193, August 20-23, 1995, Ottowa, Ontario, Canada
James H. Anderson , Mark Moir, Wait-free synchronization in multiprogrammed systems: integrating priority-based and quantum-based scheduling, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.123-132, May 04-06, 1999, Atlanta, Georgia, United States
Consensus numbers of multi-objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.211-217, June 28-July 02, 1998, Puerto Vallarta, Mexico
Progress under bounded fairness, Distributed Computing, v.12 n.4, p.197-207, September 1999
Mikhail Fomitchev , Eric Ruppert, Lock-free linked lists and skip lists, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Partha Dutta , Rachid Guerraoui , Ron R. Levy , Arindam Chakraborty, How fast can a distributed atomic read be?, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Hkan Sundell , Philippas Tsigas, Scalable and lock-free concurrent dictionaries, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Donald E. Porter , Owen S. Hofmann , Emmett Witchel, Is the optimism in optimistic concurrency warranted?, Proceedings of the 11th USENIX workshop on Hot topics in operating systems, p.1-6, May 07-09, 2007, San Diego, CA
Gary L. Peterson , Rida A. Bazzi , Gil Neiger, A gap theorem for consensus types extended abstract, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.344-353, August 14-17, 1994, Los Angeles, California, United States
Wai-Kau Lo , Vassos Hadzilacos, All of us are smarter than any of us: wait-free hierarchies are not robust, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.579-588, May 04-06, 1997, El Paso, Texas, United States
Tushar Chandra , Vassos Hadzilacos , Prasad Jayanti , Sam Toueg, Wait-freedom vs.
Jon Kleinberg , Sendhil Mullainathan, Resource bounds and combinations of consensus objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.133-143, August 15-18, 1993, Ithaca, New York, United States
Wai-Kau Lo , Vassos Hadziolacos, On the power of shared object types to implement one-resilient Consensus, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 21-24, 1997, Santa Barbara, California, United States
Richard J. Anderson, Primitives for asynchronous list compression, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.199-208, June 29-July 01, 1992, San Diego, California, United States
Michael L. Scott , William N. Scherer, Scalable queue-based spin locks with timeout, ACM SIGPLAN Notices, v.36 n.7, p.44-52, July 2001
Philippas Tsigas , Yi Zhang, Integrating non-blocking synchronisation in parallel applications: performance advantages and methodologies, Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy
Paul Attie, Wait-free Byzantine consensus, Information Processing Letters, v.83 n.4, p.221-227, 31 August 2002
Jan Friso Groote , Wim H. Hesselink , Sjouke Mauw , Rogier Vermeulen, An algorithm for the asynchronous Write-All problem based on process collision, Distributed Computing, v.14 n.2, p.75-81, April 2001
Simon Doherty , Maurice Herlihy , Victor Luchangco , Mark Moir, Bringing practical lock-free synchronization to 64-bit applications, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
linearization with an assertional proof, Distributed Computing, v.8 n.2, p.65-80, October 1994
Dimitrios S. Nikolopoulos , Theodore S. Papatheodorou, A quantitative architectural evaluation of synchronization algorithms and disciplines on ccNUMA systems: the case of the SGI Origin2000, Proceedings of the 13th international conference on Supercomputing, p.319-328, June 20-25, 1999, Rhodes, Greece
Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States
Danny Hendler , Nir Shavit, Non-blocking steal-half work queues, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Rachid Guerraoui , Benot Garbinato , Karim R. Mazouni, The GARF library of DSM consistency models, Proceedings of the 6th workshop on ACM SIGOPS European workshop: Matching operating systems to application needs, September 12-14, 1994, Wadern, Germany
Jae-Heon Yang , James H. Anderson, Time bounds for mutual exclusion and related problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.224-233, May 23-25, 1994, Montreal, Quebec, Canada
Srikanth Ramamurthy , Mark Moir , James H. Anderson, Real-time object sharing with minimal system support, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.233-242, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Wai-Kau Lo , Vassos Hadzilacos, On the power of shared object types to implement one-resilient Consensus, Distributed Computing, v.13 n.4, p.219-238, November 2000
Liqiang Wang , Scott D. Stoller, Static analysis of atomicity for programs with non-blocking synchronization, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
John Bruno , Jos Brustoloni , Eran Gabber , Avi Silberschatz , Christopher Small, Pebble: a component-based operating system for embedded applications, Proceedings of the Workshop on Embedded Systems on Workshop on Embedded Systems, p.7-7, March 29-31, 1999, Cambridge, Massachusetts
Prasad Jayanti, On the robustness of Herlihy's hierarchy, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.145-157, August 15-18, 1993, Ithaca, New York, United States
Ramesh Subramonian, Designing synchronous algorithms for asynchronous processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 29-July 01, 1992, San Diego, California, United States
Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
Hagit Attiya , Eyal Dagan, Universal operations: unary versus binary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.223-232, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Svend Frlund , Rachid Guerraoui, X-ability: a theory of replication, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.229-237, July 16-19, 2000, Portland, Oregon, United States
Xiaozhou Li , C. Greg Plaxton, On name resolution in peer-to-peer networks, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France
Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.354-362, August 14-17, 1994, Los Angeles, California, United States
Hans-J. Boehm, An almost non-blocking stack, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
James H. Anderson , Mark Moir, Universal Constructions for Large Objects, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1317-1332, December 1999
Maged M. Michael, Scalable lock-free dynamic memory allocation, ACM SIGPLAN Notices, v.39 n.6, May 2004
N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
Faith Fich , Danny Hendler , Nir Shavit, On the inherent weakness of conditional synchronization primitives, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Joseph S. Berrios , Manuel E. Bermudez, Using wait-free synchronization in the design of distributed applications, Future Generation Computer Systems, v.22 n.1, p.46-56, January 2006
Leslie Lamport, Arbitration-free synchronization, Distributed Computing, v.16 n.2-3, p.219-237, September
Faith Ellen Fich , Danny Hendler , Nir Shavit, On the inherent weakness of conditional primitives, Distributed Computing, v.18 n.4, p.267-277, March 2006
Taisuke Izumi , Toshimitsu Masuzawa, A weakly-adaptive condition-based consensus algorithm in asynchronous distributed systems, Information Processing Letters, v.100 n.5, p.199-205, December 2006
W. Craig Scratchley, Using Smalltalk for wait-free implementation of highly-concurrent objects, ACM SIGPLAN OOPS Messenger, v.4 n.4, p.44-53, Oct. 1993
Yehuda Afek , Michael Merritt , Gadi Taubenfeld, The power of multi-objects (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.213-222, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Alur , Hagit Attiya , Gadi Taubenfeld, Time-adaptive algorithms for synchronization, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.800-809, May 23-25, 1994, Montreal, Quebec, Canada
Stephen Menke , Mark Moir , Srikanth Ramamurthy, Synchronization mechanisms for SCRAMNet+ systems, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.71-80, June 28-July 02, 1998, Puerto Vallarta, Mexico
Frank Stomp , Gadi Taubenfeld, Constructing a Reliable Test&Set Bit, IEEE Transactions on Parallel and Distributed Systems, v.10 n.3, p.252-265, March 1999
Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 1997
J. Strother Moore, A Mechanically Checked Proof of a Multiprocessor Result via a Uniprocessor View, Formal Methods in System Design, v.14 n.2, p.213-228, March 1999
concurrent memory management by create and read until deletion (CaRuD), Distributed Computing, v.14 n.1, p.31-39, January 2001
Prasad Jayanti, f-arrays: implementation and applications, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Maged M. Michael, Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.491-504, June 2004
James H. Anderson , Yong-Jik Kim, A generic local-spin fetch-and--based mutual exclusion algorithm, Journal of Parallel and Distributed Computing, v.67 n.5, p.551-580, May, 2007
Ruppert, Determining consensus numbers, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.93-99, August 21-24, 1997, Santa Barbara, California, United States
Yehuda Afek , Gideon Stupp , Dan Touitou, Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.71-80, July 16-19, 2000, Portland, Oregon, United States
Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Tushar Deepak Chandra , Prasad Jayanti , King Tan, A polylog time wait-free construction for closed objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.287-296, June 28-July 02, 1998, Puerto Vallarta, Mexico
Hagit Attiya , Arie Fouren, Adaptive wait-free algorithms for lattice agreement and renaming (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.277-286, June 28-July 02, 1998, Puerto Vallarta, Mexico
Juan Alemany , Edward W. Felten, Performance issues in non-blocking synchronization on shared-memory multiprocessors, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.125-134, August 10-12, 1992, Vancouver, British Columbia, Canada
Dahlia Malkhi , Michael Merritt , Michael K. Reiter , Gadi Taubenfeld, Objects shared by Byzantine processes, Distributed Computing, v.16 n.1, p.37-48, February
H. Gao , J. F. Groote , W. H. Hesselink, Lock-free dynamic hash tables with open addressing, Distributed Computing, v.18 n.1, p.21-42, July 2005
Guy E. Blelloch , Perry Cheng , Phillip B. Gibbons, Room synchronizations, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.122-133, July 2001, Crete Island, Greece
Yehuda Afek , Gideon Stupp, Delimiting the power of bounded size synchronization objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.42-51, August 14-17, 1994, Los Angeles, California, United States
weights and contention in balancing networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.193-205, August 14-17, 1994, Los Angeles, California, United States
J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece
Maurice Herlihy , Sergio Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.324-333, August 14-17, 1994, Los Angeles, California, United States
John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada
Maurice P. Herlihy , J. E. B. Moss, Lock-free garbage collection for multiprocessors, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.229-236, July 21-24, 1991, Hilton Head, South Carolina, United States
Jaap-Henk Hoepman , Marina Papatriantafilou , Philippas Tsigas, Self-stabilization of wait-free shared memory objects, Journal of Parallel and Distributed Computing, v.62 n.5, p.818-842, May 2002
Danny Hendler , Nir Shavit, Operation-valency and the cost of coordination, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.84-91, July 13-16, 2003, Boston, Massachusetts
Hagit Attiya , Alla Gorbach , Shlomo Moran, Computing in totally anonymous asynchronous shared memory systems, Information and Computation, v.173 n.2, p.162-183, March 15, 2002
Hkan Sundell , Philippas Tsigas, Fast and lock-free concurrent priority queues for multi-thread systems, Journal of Parallel and Distributed Computing, v.65 n.5, p.609-627, May 2005
Alur , Gadi Taubenfeld, Fast timing-based algorithms, Distributed Computing, v.10 n.1, p.1-10, July 1996
Michel Raynal, Wait-free computing: an introductory lecture, Future Generation Computer Systems, v.21 n.5, p.655-663, May 2005
Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kouznetsov, Synchronizing without locks is inherently expensive, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
H. Gao , W. H. Hesselink, A general lock-free algorithm using compare-and-swap, Information and Computation, v.205 n.2, p.225-241, February, 2007
Ronald C. Unrau , Orran Krieger , Benjamin Gamsa , Michael Stumm, Experiences with locking in a NUMA multiprocessor operating system kernel, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.11-es, November 14-17, 1994, Monterey, California
Yehuda Afek , Eytan Weisberger , Hanan Weisman, A completeness theorem for a class of synchronization objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.159-170, August 15-18, 1993, Ithaca, New York, United States
Michael Saks , Fotios Zaharoglou, Wait-free
Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, ACM SIGOPS Operating Systems Review, v.36 n.5, December 2002
Danny Hendler , Nir Shavit, Operation-valency and the cost of coordination, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.84-91, July 13-16, 2003, Boston, Massachusetts
Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.241-249, August 15-18, 1993, Ithaca, New York, United States
Victor Luchangco , Mark Moir , Nir Shavit, Nonblocking k-compare-single-swap, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
Simon Doherty , David L. Detlefs , Lindsay Grove , Christine H. Flood , Victor Luchangco , Paul A. Martin , Mark Moir , Nir Shavit , Guy L. Steele, Jr., DCAS is not a silver bullet for nonblocking algorithm design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Distributed Computing, v.10 n.3, p.117-127, April 1997
Michael Merritt , Gadi Taubenfeld, Atomic m-register operations, Distributed Computing, v.7 n.4, p.213-221, May 1994
Rachid Guerraoui , Marko Vukoli, How fast can a very robust read be?, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Yehuda Afek , Eli Gafni , Adam Morrison, Common2 extended to stacks and unbounded concurrency, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared memory, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.47-58, August 10-12, 1992, Vancouver, British Columbia, Canada
Manhoi Choy , Ambuj K. Singh, Efficient fault-tolerant algorithms for distributed resource allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.535-559, May 1995
Yehuda Afek , Dalia Dauber , Dan Touitou, Wait-free made fast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.538-547, May 29-June 01, 1995, Las Vegas, Nevada, United States
Prasad Jayanti, A lower bound on the local time complexity of universal constructions, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.183-192, June 28-July 02, 1998, Puerto Vallarta, Mexico
James H. Anderson , Srikanth Ramamurthy , Kevin Jeffay, Real-time computing with lock-free shared objects, ACM Transactions on Computer Systems (TOCS), v.15 n.2, p.134-165, May 1997
Miltos Grammatikakis , Marcello Coppola , Fabrizio Sensini, Software for multiprocessor networks on chip, Networks on chip, Kluwer Academic Publishers, Hingham, MA,
Maurice Herlihy, On beyond registers: wait-free readable objects, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.26-42, August 2001, Newport, Rhode Island, United States
Hans-J. Boehm, Threads cannot be implemented as a library, ACM SIGPLAN Notices, v.40 n.6, June 2005
Maurice Herlihy , Victor Luchangco , Paul Martin , Mark Moir, Nonblocking memory management support for dynamic-sized data structures, ACM Transactions on Computer Systems (TOCS), v.23 n.2, p.146-196, May 2005
Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany
Maurice Herlihy , Beng-Hong Lim , Nir Shavit, Low contention load balancing on large-scale multiprocessors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.219-227, June 29-July 01, 1992, San Diego, California, United States
Hagit Attiya , Eyal Dagan, Improved implementations of binary universal operations, Journal of the ACM (JACM), v.48 n.5, p.1013-1037, September 2001
Kai Shen , Hong Tang , Tao Yang, Adaptive two-level thread management for fast MPI execution on shared memory machines, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.49-es, November 14-19, 1999, Portland, Oregon, United States
Hong Tang , Kai Shen , Tao Yang, Program transformation and runtime support for threaded MPI execution on shared-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.4, p.673-700, July 2000
Edouard Bugnion , Scott Devine , Kinshuk Govil , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.412-447, Nov. 1997
Alessandro Panconesi , Marina Papatriantafilou , Philippas Tsigas , Paul Vitnyi, Randomized naming using wait-free shared variables, Distributed Computing, v.11 n.3, p.113-124, August 1998
Mark Burgess , Demosthenes Skipitaris, Adaptive Locks For Frequently Scheduled Tasks With Unpredictable Runtimes, Proceedings of the 11th USENIX conference on System administration, October 26-31, 1997, San Diego, California
Yuh-Jzer Joung, Asynchronous group mutual exclusion, Distributed Computing, v.13 n.4, p.189-206, November 2000
Panagiota Fatourou , Maurice Herlihy, Read-modify-write networks, Distributed Computing, v.17 n.1, p.33-46, February 2004
Wojciech Golab , Danny Hendler , Philipp Woelfel, An O(1) RMRs leader election algorithm, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Hagit Attiya , Fabian Kuhn , C. Greg Plaxton , Mirjam Wattenhofer , Roger Wattenhofer, Efficient adaptive collect using randomization, Distributed Computing, v.18 n.3, p.179-188, February 2006
Alysson Neves Bessani , Joni da Silva Fraga , Lau Cheuk Lung, BTS: a Byzantine fault-tolerant tuple space, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Daniel Stodolsky , J. Bradley Chen , Brian N. Bershad, Fast interrupt priority management in operating system kernels, USENIX Symposium on USENIX Microkernels and Other Kernel Architectures Symposium, p.9-9, September 20-23, 1993, San Diego, California
Phuong Hoai Ha , Marina Papatriantafilou , Philippas Tsigas, Self-tuning reactive diffracting trees, Journal of Parallel and Distributed Computing, v.67 n.6, p.674-694, June, 2007
Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada
Elizabeth Borowsky , Eli Gafni , Yehuda Afek, Consensus power makes (some) sense! (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.363-372, August 14-17, 1994, Los Angeles, California, United States
Hagit Brit , Shlomo Moran, Wait-freedom vs. bounded wait-freedom in public data structures (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.52-60, August 14-17, 1994, Los Angeles, California, United States
Hagit Attiya , Vita Bortnikov, Adaptive and efficient mutual exclusion (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.91-100, July 16-19, 2000, Portland, Oregon, United States
Yehuda Afek , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, A bounded first-in, first-enabled solution to the l-exclusion problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.939-953, May 1994
Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Guy L. Steele, Jr., DCAS-based concurrent deques, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.137-146, July 09-13, 2000, Bar Harbor, Maine, United States
James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
Alon , Michael Merritt , Omer Reingold , Gadi Taubenfeld , Rebecca N. Wright, Tight bounds for shared memory systems accessed by Byzantine processes, Distributed Computing, v.18 n.2, p.99-109, December 2005
Edouard Bugnion , Scott Devine , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, ACM SIGOPS Operating Systems Review, v.31 n.5, p.143-156, Dec. 1997
Hai Huang , Padmanabhan Pillai , Kang G. Shin, Improving Wait-Free Algorithms for Interprocess Communication in Embedded Real-Time Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.303-316, June 10-15, 2002
Michel Raynal , Gadi Taubenfeld, The notion of a timed register and its application to indulgent synchronization, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
Hagit Attiya , Ophir Rachman, Atomic snapshots in
O(n
Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, ACM SIGPLAN Notices, v.28 n.7, p.73-82, July 1993
Soma Chaudhuri , Maurice Erlihy , Nancy A. Lynch , Mark R. Tuttle, Tight bounds for
Brian N. Bershad , David D. Redell , John R. Ellis, Fast mutual exclusion for uniprocessors, ACM SIGPLAN Notices, v.27 n.9, p.223-233, Sept. 1992
Gil Neiger, Failure detectors and the wait-free hierarchy (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.100-109, August 20-23, 1995, Ottowa, Ontario, Canada
Grzegorz Malewicz, A work-optimal deterministic algorithm for the asynchronous certified write-all problem, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.255-264, July 13-16, 2003, Boston, Massachusetts
Yoram Moses , Sergio Rajsbaum, The unified structure of consensus: a
layered analysis
Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.39 n.4, April 2004
Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for
Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
John Tromp , Paul Vitnyi, Randomized two-process wait-free test-and-set, Distributed Computing, v.15 n.3, p.127-135, July 2002
Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada
Mary Hall , Peter Kogge , Jeff Koller , Pedro Diniz , Jacqueline Chame , Jeff Draper , Jeff LaCoss , John Granacki , Jay Brockman , Apoorv Srivastava , William Athas , Vincent Freeh , Jaewook Shin , Joonseok Park, Mapping irregular applications to DIVA, a PIM-based data-intensive architecture, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.57-es, November 14-19, 1999, Portland, Oregon, United States
Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993
Nir Shavit , Eli Upfal , Asaph Zemach, A wait-free sorting algorithm, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.121-128, August 21-24, 1997, Santa Barbara, California, United States
Yehuda Afek , Hagit Attiya , Arie Fouren , Gideon Stupp , Dan Touitou, Long-lived renaming made adaptive, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.91-103, May 04-06, 1999, Atlanta, Georgia, United States
Steven L. Scott, Synchronization and communication in the T3E multiprocessor, ACM SIGPLAN Notices, v.31 n.9, p.26-36, Sept. 1996
Nir Shavit , Asaph Zemach, Diffracting trees (preliminary version), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.167-176, June 27-29, 1994, Cape May, New Jersey, United States
Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998
mer Eeciolu , Ambuj K. Singh, Naming symmetric processes using shared variables, Distributed Computing, v.8 n.1, p.19-38, August 1994
Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States
Freudenthal , Allan Gottlieb, Process coordination with fetch-and-increment, ACM SIGPLAN Notices, v.26 n.4, p.260-268, Apr. 1991
Panagiota Fatourou , Faith Fich , Eric Ruppert, Space-optimal multi-writer snapshot objects are slow, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Prasad Jayanti, A time complexity lower bound for randomized implementations of some shared objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.201-210, June 28-July 02, 1998, Puerto Vallarta, Mexico
Yehuda Afek , Michael Merritt , Gadi Taubenfeld , Dan Touitou, Disentangling multi-object operations (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.111-120, August 21-24, 1997, Santa Barbara, California, United States
Hong Tang , Kai Shen , Tao Yang, Compile/run-time support for threaded MPI execution on multiprogrammed shared memory machines, ACM SIGPLAN Notices, v.34 n.8, p.107-118, Aug. 1999
James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
Hany E. Ramadan , Christopher J. Rossbach , Donald E. Porter , Owen S. Hofmann , Aditya Bhandari , Emmett Witchel, MetaTM/TxLinux: transactional memory for an operating system, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
Yehuda Afek , Gideon Stupp , Dan Touitou, Long lived adaptive splitter and applications, Distributed Computing, v.15 n.2, p.67-86, April 2002
Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993
P. D.  V. Van Der Stok , A. H.  T. Janssen-Raemaekers, Real-Time Atomic Multicast Algorithms Implemented on a Shared Memory Multiprocessor, Real-Time Systems, v.24 n.1, p.55-91, January
Taisuke Izumi , Akinori Saitoh , Toshimitsu Masuzawa, Adaptive timeliness of consensus in presence of crash and timing faults, Journal of Parallel and Distributed Computing, v.67 n.6, p.648-658, June, 2007
Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Journal of the ACM (JACM), v.45 n.5, p.843-862, Sept. 1998
Paul C. Attie , E. Allen Emerson, Synthesis of concurrent programs for an atomic read/write model of computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.187-242, March 2001
Yonatan Aumann , Michael A. Bender, Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler, Distributed Computing, v.17 n.3, p.191-207, March 2005
Gunnar Hoest , Nir Shavit, Towards a topological characterization of asynchronous complexity, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.199-208, August 21-24, 1997, Santa Barbara, California, United States
Phillip B. Gibbons , Ephraim Korach, On testing cache-coherent shared memories, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.177-188, June 27-29, 1994, Cape May, New Jersey, United States
Panagiota Fatourou , Faith Fich , Eric Ruppert, A tight time lower bound for space-optimal implementations of multi-writer snapshots, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Hagit Attiya , Faith Ellen Fich , Yaniv Kaplan, Lower bounds for adaptive collect and related objects, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
Michael Hicks , Greg Morrisett , Dan Grossman , Trevor Jim, Experience with safe manual memory-management in cyclone, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
Maurice Herlihy , Sergio Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, v.291 n.1, p.55-77, 4 January
Hagit Attiya , Keren Censor, Tight bounds for asynchronous randomized consensus, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Svend Frlund , Rachid Guerraoui, Implementing E-Transactions with Asynchronous Replication, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.133-146, February 2001
James Aspnes , Gauri Shah , Jatin Shah, Wait-free consensus with infinite arrivals, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Hagit Brit , Shlomo Moran , Gadi Taubenfeld, Public data structures: counters as a special case, Theoretical Computer Science, v.289 n.1, p.401-423, 23 October 2002
Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
Hagit Attiya , Arie Fouren, Algorithms adapting to point contention, Journal of the ACM (JACM), v.50 n.4, p.444-468, July
Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994
Maurice Herlihy , Sergio Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.589-598, May 04-06, 1997, El Paso, Texas, United States
Dimitrios S. Nikolopoulos , Theodore S. Papatheodorou, The Architectural and Operating System Implications on the Performance of Synchronization on ccNUMA Multiprocessors, International Journal of Parallel Programming, v.29 n.3, p.249-282, June 2001
Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.153-162, July 2001, Hersonissos, Greece
James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.559-568, May 04-06, 1997, El Paso, Texas, United States
Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico
Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared objects, Journal of the ACM (JACM), v.42 n.6, p.1231-1274, Nov. 1995
Hagit Attiya , Arie Fouren , Eli Gafni, An adaptive collect algorithm with applications, Distributed Computing, v.15 n.2, p.87-96, April 2002
Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.174-183, May 16-18, 1993, San Diego, California, United States
James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998
Hagit Attiya , Maurice Herlihy , Ophir Rachman, Atomic snapshots using lattice agreement, Distributed Computing, v.8 n.3, p.121-132, March 1995
Gregory Chockler , Dahlia Malkhi, Active disk paxos with infinitely many processes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995
Henry G. Baker, Lively linear Lisp: look ma, no garbage!, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992
Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, ACM SIGPLAN Notices, v.40 n.10, October 2005
Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Journal of the ACM (JACM), v.50 n.6, p.922-954, November
Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
Gregory Chockler , Dahlia Malkhi, Active disk Paxos with infinitely many processes, Distributed Computing, v.18 n.1, p.73-84, July 2005
Marcos K. Aguilera, A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, v.35 n.2, June 2004
Henry G. Baker, Use-once variables and linear objects: storage management, reflection and multi-threading, ACM SIGPLAN Notices, v.30 n.1, p.45-52, Jan. 1995
Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Journal of the ACM (JACM), v.44 n.6, p.779-805, Nov. 1997
James Aspnes , Orli Waarts, Compositional competitiveness for distributed algorithms, Journal of Algorithms, v.54 n.2, p.127-151, February 2005
James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September
Henry G. Baker, Linear logic and permutation stacksthe Forth shall be first, ACM SIGARCH Computer Architecture News, v.22 n.1, p.34-43, March 1994
Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September
