same as the $γ$ used to demonstrate perturbability, and indeed it may
be that $γ'$ is very different from $γ$—in particular, it may be much

So now we expand $γ' = αβδ$, where $β$ is the magic write to the
uncovered object, and let $Λ_{k+1} = Λ_{k}αδ'$ and $Σ_{k+1} =
β Σ_{k}$, where $δ'$ consists of running all incomplete operations in
$α$ except the one that include $β$ to completion.  We've now covered
$k+1$ distinct objects in $Σ_k$.  It remains only to show that the
technical condition that any uncovered object that $π$ reads before
reading all the covered objects can't have its value changed by
inserting additional operations.

Suppose that there is a sequence of operations $κ$ such that $Λ_{k+1}
κ$ changes one of these forbidden uncovered objects.  But $Λ_{k+1} κ =
Λ_k α κ$, and so $γ'' = ακ$ changes an object that either (a) can't be
changed because of the technical condition in the induction hypothesis
for $k$, or (b) changes an object that $π$ reads before the object
covered by $β$.  In the second case, this $γ''$ changes an earlier
object that $γ'$, contradicting the choice of $γ'$.

It follows that we do in fact manage to cover $k+1$ objects while satisfying
the technical condition, and the induction hypothesis holds for $k+1$.

We can repeat this step until we've covered $n-1$ objects.  This
implies that there are at least $n-1$ objects (the space lower bound), and in the
worst case some reader reads all of them (the step complexity lower bound).

Restricted-use objects2020

The Jayanti-Tan-Toueg bound puts a hard floor under the worst-case
complexity of almost anything interesting we'd like to do wait-free in
a system that provides only historyless objects as primitives. As with
the consensus hierarchy lower bounds, we could interpret
this as a reason to demand stronger primivitives. Or we could look for
ways to bypass the JTT bound.

One approach is to modify our target objects so that they are no
longer perturbable. This can be done by limiting their use: a counter
or max register that can only change its value a limited number of
times is not perturbable, because once we hit the limit, there is no
perturbing sequence of operations that we can insert between $Λ_k$ and
$Σ_k$ in the JTT execution that changes the value returned by the
eventual reader. This observation motivated a line of work on
restricted-use max registers [5] and restricted-use
snapshots [6] that have polylogarithmic worst-case
individual step complexity assuming a polynomial limit on updates. While
restricted-use objects might not be all that exciting on their own,
they in turn have served as building blocks for implementations of
snapshots with polylogarithmic expected individual step
complexity [24] or polylogarithmic amortized individual
step complexity [82].

In this chapter, we will concentrate on the original restricted-use
max register construction of
Aspnes, Attiya, and
Censor-Hillel [5], and its extension to give
restricted-use snapshots by
Aspnes  [6].

§ MAX REGISTERS

We will start by implementing a restricted-use
register!maxmax register [5],
for which read operation returns the largest value previously written, as opposed to the last value previously written.  So after writes of 0, 3, 5, 2, 6, 11, 7, 1, 9, a read operation will return 11.

In general, max registers are perturbable objects in the sense of the Jayanti-Tan-Toueg
bound, so in the worst case a
max-register read will have to read at least $n-1$ distinct atomic
registers, giving an $n-1$ lower bound on both step complexity and
space.  But we can get around this by considering bounded max
registers, which only hold values in some range $0\dots m-1$.  These
are not perturbable because once we hit the upper bound we can no
longer insert new operations to change the value returned by a read.
This allows for a much more efficient implementation (at least in
terms of step complexity) when $m$ is not too big.

§ IMPLEMENTING BOUNDED MAX REGISTERS

This implementation is from a paper by Aspnes, Attiya, and
Censor-Hillel [5].  The same paper shows that it is in
a certain sense the only possible implementation of a wait-free
restricted max register (see §<ref>).

For $m=1$, the implementation is trivial: write does nothing and read
always returns $0$.

For larger $m$, we'll show how to paste together two max registers
and with $m_{0}$ and $m_{1}$ values
together to get a max register $r$ with $m_{0}+m_{1}$ values.  We'll
think of each value stored in the max register as a bit-vector, with
bit-vectors ordered lexicographically.  In addition to and
, we will need a 1-bit atomic register used to
choose between them.  The read procedure is straightforward and is
shown in Algorithm <ref>; essentially we just
look at , read the appropriate register, and prepend the
value of to what we get.

$\MRswitch = 0$

Max register read operation

For write operations, we have two somewhat asymmetrical cases
depending on whether the value we are writing starts with a 0 bit or a
1 bit.  These are shown in Algorithm <ref>.

$\Write(r, 0x)$
$\MRswitch = 0$
$\Write(\MRleft, x)$

$\Write(r, 1x)$
$\Write(\MRright, x)$
$\MRswitch ← 1$

Max register write operations

The intuition is that the max register is really a big tree of switch
variables, and we store a particular bit-vector in the max register by
setting to 1 the switches needed to make $\Read$ follow the path
corresponding to that bit-vector.  The procedure for writing $0x$
tests first, because once gets set to $1$, any
$0x$ values are smaller than the largest value, and we don't want them
getting written to where they might confuse particularly slow
readers into returning a value we can't linearize.  The procedure for
writing $1x$ sets second, because (a) it doesn't need to
test , since $1x$ always beats $0x$, and (b) it's not safe to
send a reader down into until some value has actually been written there.

It's easy to see that $\Read$ and $\Write$ operations both require exactly one operation per bit of the value read or written.  To show that we get linearizability, we give an explicit linearization ordering (see the paper for a full proof that this works):

* All operations that read $0$ from go in the first pile.

* Within this pile, we sort operations using the linearization
ordering for .

* All operations that read $1$ from or write $1$ to go in the second pile, which is ordered after the first pile.

* Within this pile, operations that touch are ordered
using the linearization ordering for .  Operations that
don't (which are the “do nothing” writes for $0x$ values) are placed consistently with the actual execution order.

To show that this gives a valid linearization, we have to argue first
that any $\Read$ operation returns the largest earlier $\Write$ argument and that we don't put any non-concurrent operations out of order.

For the first part, any $\Read$ in the $0$ pile returns $0 : \Read(\MRleft)$, and $\Read(\MRleft)$ returns (assuming is a
linearizable max register) the largest value previously written to
left, which will be the largest value linearized before the , or
the all-0 vector if there is no such value.  In either case we are
happy.  Any in the 1 pile returns $1 : \Read(\MRright)$.  Here
we have to guard against the possibility of getting an all-0 vector
from $\Read(\MRright)$ if
no $\Write$ operations linearize before the $\Read$.  But any $\Write$
operation that writes $1x$ doesn't set to 1 until after it
writes to , so no operation ever starts
$\Read(\MRright)$ until after at least one $\Write$ to has
completed, implying that that $\Write$ to linearizes before
the from .  So in all the second-pile operations
linearize as well.

§ ENCODING THE SET OF VALUES

If we structure our max register as a balanced tree of depth $k$, we
are essentially encoding the values $0\dots 2^{k}-1$ in binary, and
the cost of performing a read or write operation on an $m$-valued
register is exactly $k = \left\lceil\lg m\right\rceil$.  But if we are
willing to build an unbalanced tree, any prefix code will work.

The paper describes a method of building a max register where the cost
of each operation that writes or reads a value $v$ is $O(\log v)$.
The essential idea is to build a tree consisting of a rightward path
with increasingly large left subtrees hanging off of it, where each of
these left subtrees is twice as big as the previous.  This means that
after following a path encoded as $1^{k}0$, we hit a $2^{k}$-valued
max register.  The value returned after reading some $v'$ from this
max register is $v' + (2^{k}-1)$, where the $2^{k}-1$ term takes into
account all the values represented by earlier max registers in the
chain.  Formally, this is equivalent to encoding values using an
Elias gamma code, tweaked slightly by changing the prefixes
from $0^{k}1$ to $1^{k}0$ to get the ordering right.

§ UNBOUNDED MAX REGISTERS

While the unbalanced-tree construction could be used to get an
unbounded max register, it is possible that read operations might not
terminate (if enough writes keep setting 1 bits on the right path
before the read gets to them) and for very large values the cost even
of terminating reads becomes higher than what we can get out of a

Here is the snapshot-based method: if each process writes its own
contribution to the max register to a single-writer register, then we
can read the max register by taking a snapshot and returning the
maximum value.  (It is not hard to show that this is
linearizable.)  This gives an unbounded max register with read and
write cost $O(n)$.
So by choosing this in preference to the
balanced tree when $m$ is large, the cost of either operation on a max register is
$\min\left(\left\lceil\lg m\right\rceil, O(n)\right)$.

We can combine this with the unbalanced tree by terminating the right
path with a snapshot-based max register.  This gives a cost for reads and
writes of values $v$ of $O(\min(\log v, n))$.

§ LOWER BOUND

The $\min(\left\lceil\lg m\right\rceil, n-1)$ cost of a max register
read turns out to be exactly optimal.  Intuitively, we can show by a
covering argument that once some process attempts to write to a
particular atomic register, then any subsequent writes convey no
additional information (because they can be overwritten by the first
delayed write)—so in effect, no algorithm can use get more than one
bit of information out of each atomic register.  But as always,
turning this intuition into an actual proof requires a bit more work.

We will consider solo-terminating executions in
which $n-1$ writers do any number of max-register writes in some
initial prefix $Λ$, followed by a single max-register read
$π$ by process $p_n$.  Let $T(m,n)$ be the optimal reader cost for
executions with this structure with $m$ values, and let $r$ be the
first register read by process $p_n$, assuming it is running an algorithm optimized for this class of executions (we do not even require it to be correct for other executions).

We are now going split up our set of values based on which will cause
a write operation to write to $r$.  Let $S_{k}$ be the set of all sequences of
writes that only write values $≤ k$.  Let $t$ be the smallest
value such that some execution in $S_{t}$ writes to $r$ (there must be
some such $t$, or our reader can omit reading $r$, which contradicts
the assumption that it is optimal).

Case 1 Since $t$ is smallest, no execution in $S_{t-1}$ writes
to $r$.  If we restrict writes to values $≤ t-1$, we can omit
reading $r$, giving $T(t,n) ≤ T(m,n) - 1$ or $T(m,n) ≥ T(t,n)
+ 1$.

Case 2 Let $α$ be some execution in $S_{t}$ that writes
to $r$.

* Split $α$ as $α'δβ$ where $δ$ is the
first write to $r$ by some process $p_{i}$.

* Construct a new execution $α'\eta$ by letting
all the max-register writes except the one performing $δ$ finish.

* Now consider any execution $α'\eta\gammaδ$, where
$\gamma$ is any sequence of max-register writes with values $≥ t$
that excludes $p_{i}$ and $p_{n}$.  Then $p_{n}$ always sees the
same value in $r$ following these executions, but otherwise
(starting after $α'\eta$) we have an $(n-1)$-process
max-register with values $t$ through $m-1$.

* Omit the read of $r$ again to get $T(m,n) ≥ T(m-t, n-1) +

We've shown the recurrence $T(m,n) ≥ \min_{t}(\max(T(t,n),
T(m-t,n))) + 1$, with base cases $T(1,n) = 0$ and $T(m,1) = 0$.  The
solution to this recurrence is exactly $\min(\left\lceil\lg
m\right\rceil, n-1)$, which is the same, except for a constant factor on
$n$, as the upper bound we got by choosing
between a balanced tree for small $m$ and a snapshot for $m ≥
2^{n-1}$.  For small $m$, the recursive split we get is also the same
as in the tree-based algorithm: call the $r$ register and
you can extract a tree from whatever algorithm somebody gives you.  So
this says that the tree-based algorithm is (up to choice of the tree)
essentially the unique optimal bounded max register implementation for
$m ≤ 2^{n-1}$.

It is also possible to show lower bounds on randomized implementations
of max registers and other restricted-use objects.
See [5, 22, 157] for examples.

§ MAX-REGISTER SNAPSHOTS

With some tinkering, it's possible to extend the max-register
construction to get an array of max registers
that supports snapshots.  The description in this section
follows [6], with some updates to fix a bug noted in
the original paper in an erratum published by the
authors [7].

Formally, a array!maxmax array is an object $a$ that supports
an operation $\Write(a, i, v)$ that sets $a[i] ← \max(v,
a[i])$, and an
operation $\Read(a)$ that returns a snapshot of all components of the
The first step in building this beast is to do it for two components.
The resulting
max array!2-component
$2$-component max array can then
be used as a building block for larger max arrays and for fast
restricted-used snapshots in general.

A $k \times \ell$ max array $a$ is one that permits values in the range
$0 \dots k-1$ in $a[0]$ and $0 \dots \ell-1$ in $a[1]$.
We think of $a[0]$ as the of the max array and $a[1]$ as the
We'll show how to
construct such an object recursively from smaller objects of the same
type, analogous to the construction of an $m$-valued max register (which we can
think of as a $m \times 1$ max array).  The idea is to split into two pieces and as before, while representing
as a master copy stored in a max register
at the top of the tree plus cached copies at
every internal node.  These cached copies are updated by readers
at times carefully chosen to ensure linearizability.

The base of the construction is an $\ell$-valued max register
$r$, used directly as a $1 \times \ell$ max array; this is the case where
the component is trivial and we only need to store $a.\MRtail
= r$.  Here calling $\Write(a,
0, v)$ does nothing, while $\Write(a, 1, v)$ maps to $\Write(r, v)$,
and $\Read(a)$ returns
$\langle 0, \Read(r) \rangle$.

For larger values of $k$, paste a $k_\MRleft\times \ell$ max array
and a $k_\MRright \times
\ell$ max array together
to get a $(k_\MRleft+k_\MRright)\times \ell$ max array.
This construction
uses a variable as in the basic construction,
along with an $\ell$-valued max register $\MRtail$ that is used to store the
value of $a[1]$.

Calls to $\Write(a, 0, v)$ and $\Read(a)$
follow the structure of the corresponding operations for a
simple max register, with some extra work in $\Read$ to make sure that the
value in $\MRtail$ propagates into and as needed to ensure the correct value is returned.

A call to $\Write(a, 1, v)$
operation writes $\MRtail$ directly, and then calls $\Read(a)$ to
propagate the new value as well.[This call to $\Read(a)$ was
omitted in the original published version of the
algorithm [6], but was added in an erratum by the
authors [7].  Without it, the implementation
can violate linearizability in some executions.]

Pseudocode is given in Algorithm <ref>.

$\Write(a, i, v)$
$i = 0$
$v < k_\MRleft$
$a.\MRswitch = 0$
$\Write(a.\MRleft, 0, v)$

$\Write(a.\MRright, 0, v-k_\MRleft)$
$a.\MRswitch ← 1$

$\Write(a.\MRtail, v)$

$x ← \Read(a.\MRtail)$
$a.\MRswitch = 0$
$\Write(a.\MRleft, 1, x)$

$x ← \Read(a.\MRtail)$
$\Write(a.\MRright, 1, x)$
$\langle k_\MRleft, 0 \rangle + \Read(a.\MRright)$

Recursive construction of a $2$-component max array

The individual step complexity of each operation is easily computed.
Assuming a balanced tree, $\Write(a, 0, v)$ takes exactly $\ceil{\lg
steps, while $\Write(a, 1, v)$ costs exactly $\ceil{\lg \ell}$
steps plus the cost of $\Read(a)$.  Read operations are more complicated.  In the worst case, we
have two reads of $a.\MRtail$ and a write to $a.\MRright[1]$ at each
level, plus up to two operations on $a.\MRswitch$, for a total cost of at most
$(3 \ceil{\lg k} - 1) (\ceil{\lg \ell} + 2) = O(\log k \log \ell)$ steps.  This
dominates other costs in $\Write(a,1,v)$, so the asymptotic cost of
both $\Write$ and $\Read$ operations is $O(\log k \log \ell)$.

In the
special case where $k = \ell$, both writes and reads have their step
complexities squared compared
to a single-component $k$-valued max register.

§.§ Linearizability

In broad outline, the proof of linearizability follows the proof for a
simple max register.  But as with snapshots, we have to show that the
ordering of the head and tail components are consistent.

The key observation is the following lemma.

Fix some execution of a max array $a$ implemented as in
Algorithm <ref>.
Suppose this execution contains a $\Read(a)$ operation $π_\MRleft$ that returns
$v_\MRleft$ from $a.\MRleft$ and a $\Read(a)$ operation $π_\MRright$ that returns
$v_\MRright$ from $a.\MRright$.
Then $v_\MRleft[1] ≤ v_\MRright[1]$.

Both $v_\MRleft[1]$ and $v_\MRright[1]$ are values that were
previously written to their respective max arrays by $\Read(a)$
operations (such writes necessarily exist because any process that
reads $a.\MRleft$ or $a.\MRright$ writes $a.\MRleft[1]$ or
$a.\MRright[1]$ first).
From examining the code, we have that any value written
to $a.\MRleft[1]$ was read from $a.\MRtail$ before $a.\MRswitch$ was
set to $1$, while any value written to $a.\MRright[1]$ was read from
$a.\MRtail$ after $a.\MRswitch$ was set to $1$.  Since
max-register reads are non-decreasing, we have than any value written
to $a.\MRleft[1]$ is less than or equal to any value written to
$a.\MRright[1]$, proving the claim.

The rest of the proof is tedious but straightforward: we linearize the
$\Read(a)$ and $\Write(a[0])$ operations as in the max-register proof,
then fit the $\Write(a[1])$ operations in based on the values of
the reads.  The full result is:

If $a.\MRleft$ and $a.\MRright$ are linearizable max arrays, and
$a.\MRtail$ is a linearizable max register, then
Algorithm <ref> implements a linearizable max array.

It's worth noting that the same unbalanced-tree construction used in
and <ref> can be used here as well.
This makes the step complexity for $\Read(a)$ scale as $O(\log v[0]
\log v[1])$, where $v$ is the value returned.  For writes the step
complexity may depend in a complicated way on what values are being
written and to which side, but in the worst case, it is $O(\log v[0]
\log v[1])$, where $v$ is the value in the register when the write
finishes. (This is a consequence of the embedded $\Read(a)$ in

§ RESTRICTED-USE SNAPSHOTS

To build an ordinary snapshot object from $2$-component max arrays, we construct a
balanced binary tree in which each leaves holds a pointer to an individual snapshot
element and each internal node holds a pointer to a partial snapshot
containing all of the elements in the subtree of which it is the root.
The pointers themselves are non-decreasing indices into arrays of
values that consist of ordinary (although possibly very wide)
atomic registers.

When a process writes a new value to its component
of the snapshot object, it increases the pointer value in its leaf and
then propagates the new value up the tree by combining together
partial snapshots at each step, using $2$-component max arrays to
ensure linearizability.  The resulting algorithm is similar in many
ways to the lattice agreement procedure of
Inoue  [164] (see
§<ref>), except that it uses a
more contention-tolerant snapshot algorithm than double collects and
we allow processes to update their values more than once.  It is also
similar to the $f$-array
construction of Jayanti [168] for
efficient computation of array aggregates (sum, min, max, etc.) using
LL/SC, the main difference being that because the index values are
non-decreasing, max arrays can substitute for LL/SC.

Each node in the tree except the root is represented by one component
of a $2$-component max array that we can think of as being owned by
its parent, with the other component being the
node's sibling in the tree.  To propagate a value up the tree, at
each level the process takes a snapshot of the two children of the node
and writes
the sum of the indices to the node's component in its parent's max array (or to an
ordinary max register if we are at the root).  Before doing this last
write, a process will combine the partial snapshots from the two child
nodes and write the result into a separate array indexed by the sum.
In this way any process that reads the node's component can obtain the
corresponding partial snapshot in a single register operation.  At the
root this means that the cost of obtaining a complete snapshot is
dominated by the cost of the max-register read, at $O(\log v)$, where
$v$ is the number of updates ever performed.

A picture of this structure, adapted from the proceedings version of [6],
appears in Figure <ref>.  The figure depicts an
update in progress, with red values being the new values written
as part of the update.  Only some of the tables associated with the
nodes are shown.

Snapshot from max arrays; see also <cit.>

The cost of an update is dominated by the $O(\log n)$ max-array
operations needed to propagate the new value to the root.  This takes
$O(\log^2 v \log n)$ steps. Here $v$ can be taken to be the number of
update operations, which controls the maximum value on either side of
the 2-component max arrays.

The linearizability proof is trivial: linearize each update by the
time at which a snapshot containing its value is written to the root
(which necessarily occurs within the interval of the update, since we
don't let an update finish until it has propagated its value to the
top), and linearize reads by when they read the root.  This
immediately gives us an $O(\log^3 n)$ implementation—as long as we
only want to use it polynomially many times—of anything we
can build from snapshot, including counters, generalized counters, and
(by [39, 49]) any other object whose
operations all commute with or overwrite each other in a
static pattern.

§.§ Randomized and amortized snapshots

Randomization can eliminate the need to limit the number of times the
snapshot is used.
The JTT bound still applies, so there will be
occasional expensive operations, but we can spread these out randomly so that
any particular operation has low expected cost.  This gives a cost of
$O(\log^3 n)$ expected steps for an unrestricted snapshot.
This result was claimed by Aspnes and
Censor-Hillel [24], although the construction given in
the conference version of this paper (a) is based on the original,
uncorrected version of the max array from [6], (b)
incorrectly computes the running time of the algorithm, and
(c) has a rather rococo proof of linearizability that is suspect in various additional
ways.  A submitted journal version of the same
paper [25] may be more convincing.

Convincing or not, this result is largely dominated by a more recent result
by Baig  [82] that gives a deterministic snapshot
implementation with $O(\log n)$ amortized step complexity.

Note that none of these algorithms contradict the JTT lower bound: in
the worst case, each will have operations that take $Ω(n)$ steps. But
the hope is that these operations are few, and in the amortized case,
paid for by many cheap operations.
Also, even though we may beat JTT most of the time,
other lower bounds may still apply; see for
example [22, 157].

For some specific applications, further improvements are possible.  The original
max-registers paper [5] gives an implementation of
counters using a similar tree construction with only max registers
that costs only $O(\log^2 n)$ for increments; here the trick is to
observe that counters that can only be incremented by one
are much easier to make linearizable, because there is no possibility of
seeing an intermediate value that couldn't be present in a sequential
execution.  Whether it is possible to improve the cost of snapshot
is an open problem.

The common2 class, defined by Afek, Weisberger, and
Weisman [69] consists of all read-modify-write objects
where the modify functions either (a) all commute with each other or
(b) all overwrite each other.  We can think of it as the union of two
simpler classes, the set of read-modify-write objects
where all update operations commute,
commuting objectcommuting objects [66];
and the set of read-modify-write objects where all updates
produce a value that doesn't depend on the previous state,
called object!historyless
historyless objecthistoryless
objects [119]).

From §<ref>, we know that both
commuting objects and historyless objects have consensus number at
most 2, and that these objects have consensus number exactly 2
provided they supply at least one non-trivial update operation.
The main result of Afek  [69] is that commuting and
objects can all be implemented from any object with consensus number
2, even in systems with more than 2 processes.  This gives a
completeness result analogous to completeness results in
complexity theory: any non-trivial common2 object can be used to
implement any other common2 object.

The common2 conjecture was that common2 objects could also
implement any object with consensus number $2$,  This is now known to
be false [28].

The main result in the paper has two parts, reflecting the two parts
of the common2 class: a proof that 2-process consensus plus registers
is enough to implement all commuting objects (which essentially comes
down to build a generalized fetch-and-add that
returns an unordered list of all preceding operations); and a
proof that 2-process consensus plus registers is enough to implement
all overwriting objects (which is equivalent to showing that we can
implement swap objects).  The construction of the generalized
fetch-and-add is pretty nasty, so we'll concentrate on the
implementation of swap objects.  We will also skip the swap
implementation in [69], and instead describe, in
and <ref>, a simpler
(though possibly less efficient) algorithm from a later paper by Afek,
Morrison, and Wertheim [52].  Before we do this, we'll
start with some easier results from the older paper, including an
implementation of $n$-process test-and-set from $2$-process consensus.
This will show that anything we can do with test-and-set we can do
with any common2 object.

§ TEST-AND-SET AND SWAP FOR TWO PROCESSES

The first step is to get test-and-set.

Algorithm <ref> shows how to turn $2$-process
consensus into $2$-process test-and-set.  The idea is that whoever
wins the consensus protocol wins the test-and-set.  This is
linearizable, because if I run $\TwoTAS$ before you do, I win the
consensus protocol by validity.

$\TwoConsensus(\MyId) = \MyId$

Building $2$-process TAS from $2$-process consensus

Once we have test-and-set for two processes, we can easily get
one-shot swap for two processes.  The trick is that a one-shot swap
object always returns $⊥$ to the first process to access it and
returns the other process's value to the second process.  We can
distinguish these two roles using test-and-set and add a register to
send the value across.  Pseudocode is in
Algorithm <ref>.

$a[\MyId] = v$
$\TwoTAS() = 0$

$a[¬ \MyId]$

Two-process one-shot swap from TAS

§ BUILDING N-PROCESS TAS FROM 2-PROCESS TAS

To turn the $\TwoTAS$ into full-blown $n$-process $\TAS$, start by
staging a
tournament along the lines of [203]
(§<ref>).  Each process walks up a tree of
nodes, and at each node it attempts to beat every process from the
other subtree using a $\TAS_2$ object (we can't just have it fight one
process, because we don't know which one process will have won the
other subtree, and our $\TAS_2$ objects may only work for two
specific processes).  A process drops out if it ever sees a $1$.  We can
easily show that at most one process leaves each subtree with all
zeros, including the whole tree itself.

Unfortunately, this process does not give a linearizable
test-and-set object.  It is possible that $p_1$ loses early to $p_2$,
but then $p_3$ starts (elsewhere in the tree) after $p_1$ finishes,
and races to the top, beating out $p_2$.  To avoid this, we can
follow [69] and add a bit that locks out
latecomers.[The original version of this trick is from an
earlier paper [37], where the bit is
implemented as an array of single-writer registers.]

The resulting
construction looks something like Algorithm <ref>.
This gives a slightly different interface from straight ; instead
of returning $0$ for winning and $1$ for losing, the algorithm returns
$⊥$ if you win and the of some process that beats you
if you lose.[Note that this process may also be a loser, just
one that made it further up the tree than you did.  We can't
expect to learn the id of the ultimate winner, because that would
solve $n$-process consensus.] It's not hard to see that this gives a linearizable
test-and-set after translating the values back to $0$ and $1$ (the
trick for linearizability is that any process that wins saw an empty
gate, and so started before any other process finished).  It
also sorts the processes into a rooted tree, with each
process linearizing after its parent (this latter claim is a
little trickier, but basically comes down to a loser linearizing after
the process that defeated it either on or on one of the
$\TwoTAS$ objects).

check the gate
$\AWWgate \ne ⊥$

$\AWWgate ← i$
Do tournament, returning $\Id$ of whoever I lose to
$\AWWnode ← $ leaf for $i$
$\AWWnode \ne \DataSty{root}$
$j$ whose leaf is below sibling of $\AWWnode$
$\TwoTAS(t[i,j]) = 1$

$\AWWnode ← \AWWnode.\DataSty{parent}$

I win!

Tournament algorithm with gate

This algorithm is kind of expensive: the losers that drop out early
are relatively lucky, but the winning process has to win a $\TwoTAS$
against everybody, for a total of $Θ(n)$ $\TestAndSet$ operations.
We can reduce the cost to $O(\log n)$ if our $\TwoTAS$ objects allow
arbitrary processes to execute them.  This is done, for example, in
the RatRace test-and-set implementation of
Alistarh  [14], using a randomized
implementation of $\TwoTAS$ due to Tromp and Vitányi [223]
(see §<ref>).

§ OBSTRUCTION-FREE SWAP FROM TEST-AND-SET

We'll start by describing the “strawman algorithm” from the AMW
paper.  This is presented by the authors as a stepping-stone to their
real algorithm, which we will describe below in

The code is given in Algorithm <ref>.  This
implements a swap object that is linearizable but not wait-free.

$i ← 0$

Look for a starting point
$\TestAndSet(s_i) = 1$

$i ← i+1$

$v_i ← v$
Check if we've been blocked
$\TestAndSet(t_i) = 0$

We win, find our predecessor
$j ← i-1$ $0$
$\TestAndSet(t_j) = 1$
Use this value

Didn't find anybody, we are first

Pick a new start and try again

Obstruction-free swap from test-and-set

This algorithm uses two infinite arrays $s$ and $t$ of test-and-set
objects and an infinite array $r$ of atomic registers.  The $s_i$
objects are essentially being used to implement a fetch-and-increment,
and if we have a fetch-and-increment lying around we can
replace the loop at
Line <ref> with an
operation on that object instead.  The $r_i$ registers record values
to return.  The $t_i$ registers implement a block/pass mechanism where
a later process can force an earlier process to try again if it didn't
record its value in time.  This solves the problem of a process going
to sleep after acquiring a particular slot $i$ from the
fetch-and-increment but before writing down a value that somebody else
can use.

The algorithm is obstruction-free, because in any reachable
configuration, only finitely many test-and-sets have been accessed, so
there is some value $i$ with $s_j = t_j = 0$ for all $j ≥ i$.  A process running in
isolation will eventually hit one of these slots, win both
test-and-sets, and return.

For linearizability, the value of $i$ when each operation returns
gives an obvious linearization ordering.  This ordering is consistent
with the observed history, because if I finish with value $i_1$ before
you start, then at the time that I finish all $s_j$ for $j ≤ i_1$ have
$s_j = 1$.  So you can't win any of them, and get a slot $i_2 > i_1$.
But we still have to show that the return values make sense.

Consider some swap operation $π$.

Suppose that $π$ starts at position
$i$ and wins every $t_j$ down to position $k$, where it loses.  Then
no other operation wins any $t_j$ with $k < j < i$, so there is no
process that leaves with any slot between $k$ and $i$.  In addition,
the operation $π'$that did win $t_k$ must have taken slot $k$ in
Line <ref>, because any
other process would have needed to win $t_{k+1}$ before attempting to
win $t_k$.  So $π'$ linearizes immediately before $π$, which is good,
because $π$ returns the value $v_k$ that $π'$ wrote before it won

Alternatively, suppose that $π$ never loses $t_j$ for any $j ≤ i$.
Then no other operation takes a slot less than $i$, and $π$ linearizes
first.  In this case, it must return $⊥$, which it does.

§ WAIT-FREE SWAP FROM TEST-AND-SET

Now we want to make the strawman algorithm wait-free.  The basic idea
is similar: we will have an ordered collection of test-and-set
objects, and a process will move right until it can capture one that
determines its place in the linearization ordering, and then it will
move left to block any other processes from taking an earlier place
unless they have already written out their values.  To avoid
starvation, we assign a disjoint collection of test-and-set objects to
each operation, so that every operation eventually wins one of its own
test-and-sets.  Unfortunately this only works if we make the ordering
dense, so that between each pair of test-and-sets there are infinitely
many other test-and-sets.

AMW do this in terms of a binary tree, but I find it easier to think
of the test-and-sets as being indexed by dyadic
rationals strictly between $0$ and $1$.[The two representations are
isomorphic: make each value $k/2^q$ be the parent of $k/2^q ±
1/2^{q+1}$.] The idea
is that the $i$-th operation to start executing the swap object will
use test-and-sets $t_q$ where $q = k/2^i$ for all odd $k$ in the range
$1\dots 2^i-1$.  In order to avoid having to check the infinitely many
possible values smaller than $q$, we will use two auxiliary objects: a
readable fetch-and-increment $\AMWmaxDepth$ that hands out denominators
and tracks the largest denominator used so far, and a max register
$\AMWaccessed$ that keeps track of the largest position accessed so

AMW implement $\AMWaccessed$ using a snapshot, which we will do as
well to avoid complications from trying to build a max register out of
an infinitely deep tree.[The issue is not so much that we
can't store arbitrary dyadics, since we can encode them using an
order-preserving prefix-free code, but that, without some sort of
helping mechanism, a read running concurrently with endlessly
increasing writes (e.g. $1/2, 3/4, 7/8, \dots$) might not be
wait-free.  Plus as soon as the denominator exceeds
$2^n$, which happens after only $n$ calls to $\Swap$, $O(n)$-step snapshots are cheaper anyway.]
Note that AMW don't call this data structure a max register, but we
will, because we like max registers.

Code for the swap procedure is given in
Algorithm <ref>.

Pick a new row just for me
$\AMWdepth ← \FuncSty{fetchAndIncrement}(\AMWmaxDepth)$
Capture phase

Pick leftmost node in my row greater than
$\AMWcap ← \min \SetWhere{x}{\text{$x = k/2^\AMWdepth$ for odd $k$}, x > \AMWaccessed}$
Post my value
$\AMWreg[\AMWcap] ← v$
Try to capture the test-and-set
$\AMWwin ← \TestAndSet(\AMWtst[\AMWcap]) = 0$
$\FuncSty{writeMax}(\AMWaccessed, \AMWcap)$

Return phase
Max depth reached by anybody left of $\AMWcap$
$\AMWmaxPreviousDepth ← \Read(\AMWmaxDepth)$
$\AMWret ← \AMWcap$
Block previous nodes until we find one we can take
$\TestAndSet(\AMWtst[\AMWret]) = 1$
$\AMWret ← \max \SetWhere{x = k/2^q}{q ≤
\AMWmaxPreviousDepth, \text{$k$ odd}, x < \AMWret}$
$\AMWret < 0$

Wait-free swap from test-and-set [52]

To show Algorithm <ref> works, we need the
following technical lemma, which, among other things, implies that
node $1-2^{\AMWdepth}$ is
always available to be captured by the process at depth $\AMWdepth$.
This is essentially just a restatement of Lemma 1
from [52].

For any $x = k/2^q$, where $k$ is odd, no process attempts to capture
any $y ∈ [x,x+1/2^q)$ before some process writes $x$ to $\AMWaccessed$.

Suppose that the lemma fails, let $y = \ell/2^r$ be the first node captured
in violation of the lemma, and let $x = k/2^q$ be such that $y ∈
[x,x+1/2^q)$ but $x$ has not been written to $\AMWaccessed$ when
$y$ is captured.  Let $p$ be the process that captures $y$.

Now consider $y' = x-1/2^r$, the last node to the left of
$x$ at the same depth as $y$.  Why didn't $p$ capture $y'$?

One possibility is that some other process $p'$ blocked $y'$ during
its return phase.  This $p'$ must have captured a node $z > y'$.
If $z > y$, then $p'$ would have blocked $y$ first, preventing $p$
from capturing it.  So $y' < z < y$.

The other possibility is that $p$ never tried to capture $y'$,
because some other process $p'$ wrote some value $z > y'$ to
$\AMWaccessed$ first.  This value $z$ must also be less than $y$
(or else $p$ would not have tried to capture $y$).

In both
cases, there is a process $p'$ that captures a value $z$ with $y' <
z < y$, before $p$ captures $y$ and thus before anybody writes $x$
to $\AMWaccessed$.

Since $y' < x$ and $y' < z$, either $y' < z < x$ or $y' < x < z$.  In the
first case, $z ∈ [y',y'+1/2^r)$ is captured before $y'$ is written
to $\AMWaccessed$.
In the second case $z ∈ [x,x+1/2^q)$ is captured before $x$ is
written to $\AMWaccessed$.  Either way, $y$ is not the
first capture to violate the lemma, contradicting our
initial assumption.

Using Lemma <ref>, it is
straightforward to show that Algorithm <ref> is
wait-free.  If I get $q$ for my value of $\AMWdepth$, then no process
will attempt to capture any $y$ in $[1-2^q,1)$ before I write $1-2^q$
to $\AMWaccessed$.  But this means that nobody can block me from
capturing $1-2^q$, because processes can only block values smaller than
the one they already captured.  I also can't get stuck in the return
phase, because there are only finitely many values with denominator
less than $2^{\AMWmaxPreviousDepth}$.

It remains to show that the implementation is linearizable.  The obvious
linearization ordering is given by sorting each operation $i$ by its
captured node $\AMWcap$.  Linearizability requires then that if we
imagine a directed graph containing an edge $ij$ for each pair of
operations $i$ and $j$ such
that $i$ captures $\AMWcap_i$ and returns $\AMWreg[\AMWcap_j]$, then this graph
forms a path that corresponds to this linearization ordering.

Since each process only returns one value, it trivially holds
that each node in the graph has out-degree at most $1$.
For the in-degree, suppose that we have operations $i$, $j$, and $k$
with $\AMWcap_i < \AMWcap_j < \AMWcap_k$ such that $j$ and $k$ both
return $\AMWreg[\AMWcap_i]$.  Before $k$ reaches $\AMWtst[\AMWcap_i]$,
it must first capture all the test-and-sets between $\AMWcap_i$ and
$\AMWcap_k$ that have depth less than or equal to
$\AMWmaxPreviousDepth_k$.  This will include $\AMWtst[\AMWcap_j]$,
because $j$ must write to $\AMWmaxDepth$ before doing anything, and
this must occur before $k$ starts the return phase if $j$ sees a value
of $\AMWaccessed$ that is less that $\AMWcap_k$.

A similar argument show that there is at most one process that returns
$⊥$; this implies that there is at most one process with out-degree

So now we have a directed graph where every process has in-degree and
out-degree at most one, which implies that each weakly-connected
component will be a path.  But each component will also have exactly
one terminal node with out-degree $0$.  Since there is only one such
node, there is only one component, and the entire graph is a single
path.  This concludes the proof of linearizability.

§ IMPLEMENTATIONS USING STRONGER BASE OBJECTS

The terrible step complexity of known wait-free implementations of
Common2 objects like $\Swap$ or $\FetchAndIncrement$ from $2$-process
consensus objects and registers has led to work on finding better
implementations assuming stronger base objects.  Using
load-linked/store-conditional, Ellen and Woelfel [117]
provide implementations of several
Common2 objects, including $\FetchAndIncrement$, $\FetchAndAdd$, and
$\Swap$ that all have $O(\log n)$ individual step
complexity.[What they actually implement is the ability to do
fetch-and-$f$, where $f$ is any binary associative function,
using an object they call an aggregator.
Each of these objects is obtained by choosing an appropriate $f$.]
This is
know to be optimal due to a lower bound of
Jayanti [167].

The lower bound applies a fortiori to the case where we don't
have LL/SC or CAS and have to rely on 2-process consensus objects.
But it's not out of the question that there is a matching upper bound
in this case.

Randomized consensus and test-and-set2020

We've seen that we can't solve consensus in an asynchronous
system message-passing or shared-memory system with one crash failure [130, 173], but that
the problem becomes solvable using failure
detectors [103].  An alternative that also allows us to
solve consensus is to allow the processes to use randomization, by
providing each process with a local coin that can generate
random values that are immediately visible only to that process.
The resulting
randomized consensus problem replaces
the termination requirement with
probabilistic termination: all processes terminate with
probability $1$.  The agreement and validity requirements remain the

In this chapter, we will describe how randomization interacts with the
adversary, give a bit of history of randomized consensus, and then
concentrate on recent algorithms for randomized consensus and the
closely-related problem of randomized test-and-set.
Much of the material in this chapter is adapted from notes
for a previous course on randomized algorithms [60] and
a few of my own papers [62, 27, 61].

§ ROLE OF THE ADVERSARY IN RANDOMIZED ALGORITHMS

Because randomized processes are unpredictable, we need to become a
little more sophisticated in our handling of the adversary.  As in
previous asynchronous protocols, we assume that the adversary has
control over timing, which we model by allowing the adversary to
choose at each step which process performs the next operation.  But
now the adversary may do so based on knowledge of the state of the
protocol and its past evolution.  How much knowledge we give the
adversary affects its power.  Several classes of adversaries have been
considered in the literature; ranging from strongest to weakest, we

* An adversary!adaptiveadaptive adversary.  This
adversary is a function from the state of the system to the set of
processes; it can see everything that has happened so far (including
coin-flips internal to processes that have not yet been revealed to
anybody else), but can't predict the future.  It's known that an
adaptive adversary can force any randomized consensus protocol to take
$Θ(n^2)$ total steps [20].  The adaptive
adversary is also called a
strong adversary following a foundational paper of
Abrahamson [19].

* An
intermediate adversary
weak adversary [19]
is one that limits the adversary's ability to observe or control the system in
some way, without completely eliminating it.
For example, a
content-oblivious adversary [93]
value-oblivious adversary [65]
is restricted from seeing the values contained in registers or pending
write operations and from observing the internal states of processes
directly.  A
location-oblivious adversary [62]
can distinguish between values and the types of pending operations,
but can't discriminate between pending operations based one which
register they are operating on.
These classes of adversaries are modeled by imposing an equivalence
relation on partial executions and insisting that the adversary make
the same choice of processes to go next in equivalent situations.
Typically they arise because somebody invented a consensus protocol
for the oblivious adversary (described below) and then looked for the next most
powerful adversary that still let the protocol work.

Weak adversaries often allow much faster consensus protocols than
adaptive adversaries.  Each of the above adversaries permits consensus
to be achieved in $O(\log n)$ expected individual work using an
appropriate algorithm.  But from a mathematical standpoint, weak
adversaries are a bit messy, and once you start combining algorithms
designed for different weak adversaries, it's natural to move all the
way down to the weakest reasonable adversary, the oblivious adversary.

* A adversary!obliviousoblivious adversary
has no ability to observe the system at all; instead, it fixes a
sequence of process ids in advance, and at each step the next process
in the sequence runs.

We will
describe below a protocol that guarantees
$O(\log \log n)$ expected individual work for an oblivious
It is not
known whether this is optimal; in fact, is is consistent with the best
known lower bound (due to Attiya and Censor [20])
that consensus can be solved in $O(1)$ expected individual steps
against an oblivious adversary.

Each of these adversaries is defined based on choosing steps of
particular objects, with particular constraints on knowledge based on
the states of those objects. This interacts badly with
abstractions like linearizability: an adversary might be able to play
games with the internals of an implementation of an object that allows
it more power than it would have with an actual sequential version of the
object. So even though linearizable implementations are
indistinguishable from sequential objects for deterministic protocols,
for randomized protocols they can give very different results for both
adaptive and oblivious adversaries [141]; and in the
specific case of consensus, it can be shown that there are randomized
consensus protocols that terminate with probability $1$ against an
adaptive adversary when implemented with atomic registers, but fail
to terminate with nonzero probability when implemented using an
arbitrary linearizable implementation [156].

These results don't necessarily imply the failure of any specific consensus
protocol implemented using a specific atomic register simulation,
but they do justify suspicion.  The easiest way to
deal with this suspicion is to assume that our atomic registers are,
in fact, atomic, so that's what we will do here.

§ HISTORY

The use of randomization to solve consensus in an asynchronous system
with crash failures
was proposed by
Ben-Or [85] for a message-passing model.  Chor, Israeli,
and Li [96] gave the first wait-free consensus protocol for a
shared-memory system, which assumed a particular kind of
weak adversary.  Abrahamson [19] defined strong and weak
adversaries and gave the first wait-free consensus protocol for a
strong adversary; its expected step complexity was
$Θ\left(2^{n^2}\right)$.  After failing to show that exponential
time was necessary, Aspnes and Herlihy [38]
showed how to do consensus in $O(n^4)$ total step complexity, a value that was
soon reduced to $O(n^2 \log n)$ by Bracha and
Rachman [88].  This remained the best known bound for
the strong-adversary model until Attiya and
Censor [20] showed matching $Θ(n^2)$ upper and
lower bounds on total step complexity.  A later paper by Aspnes and Censor [21]
showed that it was also possible to get an $O(n)$ bound on individual
step complexity.

For weak adversaries, the best known upper bound on individual step
complexity was $O(\log
n)$ for a long time [93, 65, 62],
with an $O(n)$ bound on total step complexity for some
models [62].
More recent work has lowered the bound to $O(\log \log n)$, under the
assumption of an oblivious adversary [61].
No non-trivial lower bound on expected
individual step complexity is known, although there is a known lower
bound on the distribution of of the individual step
complexity [23].

In the following sections, we will concentrate on the more recent
weak-adversary algorithms.  These have the advantage of being fast
enough that one might reasonably consider using them in practice,
assuming that the weak-adversary assumption does not create trouble,
and they are also require less probabilistic machinery to analyze than
the strong-adversary algorithms.

§ REDUCTION TO SIMPLER PRIMITIVES

To show how to solve consensus using randomization, it helps to split
the problem in two: we will first see how to detect when we've
achieved agreement, and then look at how to achieve agreement.

§.§ Adopt-commit objects

Most known randomized consensus protocols have a round-based structure
that alternates between generating and detecting agreement.
Gafni [134] proposed
adopt-commit protocoladopt-commit protocols as a tool
for detecting agreement, and these protocols were later abstracted as
adopt-commit objectadopt-commit
objects [193, 35].
The version described here is largely taken from [27], which
shows bounds on the complexity of adopt-commit objects.

An adopt-commit object
supports a single operation, ($u$),
where $u$ is an input from a set of $m$ values.
The result of this operation is an output of the form $(\ACcommit,v)$
or $(\ACadopt,v)$,
where the second component is a value from this set
and the first component
is a decision bit that indicates whether the
process should decide value $v$ immediately or adopt it as its
preferred value in later rounds of the protocol.

The requirements for an adopt-commit object are the usual requirements
of validity and termination, plus:

* coherenceCoherence.  If the output of some
operation is $(\ACcommit,v)$,
then every output is either $(\ACadopt,v)$ or $(\ACcommit,v)$.

* convergenceConvergence.  If all inputs are $v$, all
outputs are $(\ACcommit,v)$.

These last two requirement replace the agreement property of
consensus.  They are also strictly weaker than consensus, which means
that a consensus object (with all its output labeled ) is
also an adopt-commit object.

The reason we like adopt-commit objects is that they allow the simple
consensus protocol shown in
Algorithm <ref>.

$\ACpref ← \DataSty{input}$

$r ← 1 \dots \infty$
$(b, \ACpref) ← \AdoptCommit(AC[r], \ACpref)$
$b = \ACcommit$

do something to generate a new

Consensus using adopt-commit

The idea is that the adopt-commit takes care of ensuring that once
somebody returns a value (after receiving ), everybody else
who doesn't return adopts the same value (follows from coherence).
Conversely, if everybody already has the same value, everybody returns
it (follows from convergence).  The only missing piece is the part
where we try to shake all the processes into agreement.  For this we
need a separate object called a conciliator.

§.§ Conciliators

Conciliators are a weakened version of randomized consensus that
replace agreement
with agreement!probabilisticprobabilistic agreement:
the processes can disagree sometimes, but must agree with
constant probability despite interference by the adversary.  An
algorithm that satisfies termination, validity, and probabilistic
agreement is called a conciliator.[Warning: This
name has not really caught on in the general
theory-of-distributed-computing community, and so far only appears in
papers that have a particular researcher as a
co-author [61, 27, 62, 8].
Unfortunately, there doesn't seem to be a better
name for the same object that has caught on.  So we are stuck with it
for now.]

The important feature of conciliators is that if we plug a conciliator
that guarantees agreement with probability at least $δ$ into
Algorithm <ref>, then on average we
only have to execute the loop $1/δ$ times before every process
agrees.  This gives an expected cost equal to $1/δ$ times the
total cost of and the conciliator.  Typically we will aim
for constant $δ$.

§ IMPLEMENTING AN ADOPT-COMMIT OBJECT

What's nice about adopt-commit objects is that they can be implemented
deterministically.  Here we'll give a simple adopt-commit object for
two values, $0$ and $1$.  Optimal (under certain assumptions)
constructions of $m$-valued adopt-commits can be found
in [27].

Pseudocode is given in Algorithm <ref>.

$a[0]$, $a[1]$, initially $\False$; , initially $⊥$
$a[v] ← 1$
$\ACproposal = ⊥$
$\ACproposal ← v$

$v ← \ACproposal$

$a[¬ v] = \False$
$(\ACcommit, v)$

$(\ACadopt, v)$

A 2-valued adopt-commit object

Structurally, this is pretty similar to a splitter (see
§<ref>), except that we use values instead of
process ids.

We now show correctness.
Termination and validity are trivial.  For coherence,
observe that if I return $(\ACcommit, v)$ I must have read
$a[¬ v] = \False$ before any process with $¬ v$ writes $a[¬
v]$; it follows that all such processes will see $\ACproposal \ne
⊥$ and return $(\ACadopt, v)$.  For convergence, observe that if all
processes have the same input $v$, they all write it to $\ACproposal$
and all observe $a[¬ v] = \False$, causing them all to return
$(\ACcommit, v)$.

§ CONCILIATORS AND SHARED COINS

For an adaptive adversary, the usual way to implement a conciliator is
from a coin!weak sharedshared coin!weakweak
shared coin [38], which is basically a
non-cryptographic version of the coin!commoncommon
coin [213] found in many cryptographic Byzantine agreement protocols.
Formally, a weak shared coin is
an object that has no inputs and returns either $0$ or $1$ to all processes with some
minimum probability $δ$.  By itself this does not give validity, so
converting a weak shared coin into a conciliator requires extra
machinery to bypass the coin if the processes that have accessed the
conciliator so far are all in agreement; see
Algorithm <ref>.  The intuition is that having
some processes (who all agree with each other) skip the shared coin is not a problem, because with
probability $δ$ the remaining processes will agree with them as well.

binary registers $r_0$ and $r_1$, initially 0;

weak shared coin $\SharedCoin$
$r_v \leftarrow 1$
$r_{\neg v} = 1$

Shared coin conciliator from [62]

This still leaves the problem of how to build a shared coin.  In the
message-passing literature, the usual approach is to use
cryptography,[For example, Canetti and
Rabin [101] solved Byzantine agreement in $O(1)$ time
building a shared coin on top of secret sharing.]
but because we are assuming an arbitrarily powerful adversary, we
can't use cryptography.

If we
don't care how small $δ$ gets, we could just have each process flip
its own local coin and hope that they all come up the same.
(This is more or less what was done by
Abrahamson [19].)
But that might take a while.  If we aren't willing to wait
exponentially long, a better approach is to combine many individual
local coins using some sort of voting.

A version of this approach, based on a random walk, was used by
Aspnes and Herlihy [38] to get consensus in (bad)
polynomial expected time against an adaptive adversary.  A better
version was developed by Bracha and Rachman [88].  In
their version, each process repeatedly generates a random $±1$ vote
and adds it to a common pool (which just means writing the sum and
count of all
its votes so far out to a single-writer register).  Every $Θ(n / \log
n)$ votes, the process does a collect (giving an overhead of $Θ(\log
n)$ operations per vote) and checks to see if the total number of
votes is greater than a $Θ(n^2)$ threshold.  If it is, the process
returns the sign of the total vote.

Bracha and Rachman showed that despite processes seeing different
combinations of votes (due to the collects running at possibly very
different speeds), the difference between what each process sees and
the actual sum of all votes ever generated is at most $O(n)$ with high
probability.  This means that if the total vote is more than $cn$ from
$0$ for some $c$, which occurs with constant probability, then every
processes is likely to return the same value.  This gives a weak
shared coin with constant bias, and thus also a consensus protocol,
that runs in $O(n^2 \log n)$ expected total steps.

This remained the best known protocol for many years, leaving an
annoying gap between the upper bound and the best known lower bound of
$Ω(n^2/\log^2 n)$ [58].  Eventually,
Attiya and Censor [20] produced an entirely new
argument to bring the lower bound up to $Ω(n^2)$ and at the same time
gave a simple tweak to the Bracha-Rachman protocol to bring the upper
bound down to $O(n^2)$, completely settling (up to constant factors)
the asymptotic expected total step complexity of strong-adversary consensus.
But the question of how quickly one could solve weak-adversary
adversary consensus remained (and still remains) open.

§ A ONE-REGISTER CONCILIATOR FOR AN OBLIVIOUS ADVERSARY

Impatient first-mover conciliator
from [62]

register $r$, initially $⊥$
$k \gets 0$
$r = ⊥$
write $v$ to $r$

do a dummy operation

$k \gets k+1$

Algorithm <ref> implements
a conciliator for an oblivious adversary[Or any adversary
weak enough not to be able to
block the write based on how the coin-flip turned out.]
using a single register.
This particular construction is taken from [62],
and is based on an earlier algorithm of Chor, Israeli, and
Li [96].  The cost of this algorithm is expected $O(n)$ total work
and $O(\log n)$ individual work.
Later (§<ref>), we will see a different
algorithm [61] that reduces the individual work to $O(\log \log n)$,
although the total work for that algorithm may be $O(n \log \log n)$.

The basic idea is that processes alternate between reading
a register $r$ and (maybe) writing to the register; if a process reads
a non-null value from the register, it returns it.  Any other process
that reads the same non-null value will agree with the first process;
the only way that this can't happen is if some process writes a
different value to the register before it notices the first write.

The random choice of whether to write the register or not avoids this
problem.  The idea is that even though the adversary can schedule a
write at a particular time, because it's oblivious, it won't be able
to tell if the process wrote (or was about to write) or did a no-op

The basic version of this algorithm, due to Chor, Israeli,
and Li [96], uses a fixed $\frac{1}{2n}$ probability of
writing to the register.  So once some process writes to the register,
the chance that any of the remaining $n-1$ processes write to it
before noticing that it's non-null is at most $\frac{n-1}{2n} < 1/2$.
It's also not hard to see that this algorithm uses $O(n)$ total
operations, although it may be that one single process running by
itself has to go through the loop $2n$ times before it finally writes
the register and escapes.

Using increasing probabilities avoids this problem, because any
process that executes the main loop $\ceil{\lg n} + 1$ times will write the
register.  This establishes the $O(\log n)$ per-process bound on
operations.  At the same time, an $O(n)$ bound on total operations
still holds, since each write has at least a $\frac{1}{2n}$ chance of
The price we pay for the improvement is that
we increase the chance that an initial value written to the
register gets overwritten by some high-probability write.  But the
intuition is that the probabilities can't grow too much, because the
probability that I write on my next write is close to the sum of the
probabilities that I wrote on my previous writes—suggesting that if
I have a high probability of writing next time, I should have done a
write already.

Formalizing this intuition requires a little bit of work.
Fix the schedule, and let $p_i$ be the probability that the $i$-th
write operation in this schedule succeeds.
Let $t$ be the least value for which $\sum_{i=1}^{t} p_i ≥ 1/4$.
We're going to argue that with constant probability
one of the first $t$ writes succeeds, and that the
next $n-1$ writes by different processes all fail.

The probability that none of the first $t$ writes succeed is

\begin{align*}
\prod_{i=1}^t (1-p_i)
&≤ \prod_{i=1}^t e^{-p_i}
\\&= \exp\left(\sum_{i=1}^t p_i\right)
\\&≤ e^{-1/4}.
\end{align*}

Now observe that if some process $p$ writes at or before the $t$-th write,
then any process $q$ with a pending write either did no writes previously,
or its last write was among the first $t-1$ writes, whose
probabilities sum to less than $1/4$.
In either case,
$q$ has a $\sum_{i\in S_q} p_i + \frac{1}{2n}$ chance of
writing on its pending attempt, where $S_q$ is the set of indices in
$1\dots t-1$ where $q$ previously attempted to write.

Summing up these probabilities over all processes gives
a total of
$\frac{n-1}{2n} + \sum_q \sum_{i \in S_q} p_i ≤ 1/2 + 1/4 = 3/4$.
So with probability at least $e^{-1/4}(1-3/4) = e^{-1/4}/4$, we get

§ SIFTERS

A faster conciliator can be obtained using a sifter, which
is a mechanism for rapidly discarding processes using
randomization [1] while keeping at least one process
The simplest sifter has each process either write a register (with
low probability) or read it (with high probability); all writers and
all readers that see $⊥$ continue to the next stage of the protocol,
while all readers who see a non-null value drop out.
If the probability of writing is tuned carefully, this
will reduce $n$ processes to at most $2\sqrt{n}$ processes on average;
by iterating this mechanism, the expected number of remaining
processes can be reduced to $1+ε$ after $O(\log \log n + \log (1/ε))$

As with previous implementations of test-and-set (see
Algorithm <ref>),
it's often helpful to have a sifter return
not only that a process lost but which process it lost to.  This gives
the implementation shown in Algorithm <ref>.

$r ← \Id$

A sifter

To use a sifter effectively, $p$ should be tuned to match the number
of processes that are likely to use it.  This is because of the
following lemma:

Fix $p$, and let $X$ processes executed a sifter with parameter
$p$.  Let $Y$ be the number of processes for which the sifter
returns $⊥$.  Then

\begin{equation}
\ExpCond{X}{Y} ≤ pX + \frac{1}{p}.
\label{eq-lemma-sifter}
\end{equation}

In order to return $⊥$, a process must either (a) write to $r$, which
occurs with probability $p$, or (b) read $r$ before any other process
writes to it.  The expected number of writers, conditioned on $X$, is
exactly $pX$.  The expected number of readers before the first write
has a geometric distribution truncated by $X$.  Removing the truncation
gives exactly $\frac{1}{p}$ expected readers, which is an upper bound
on the correct value.

For $n$ initial processes, the choice of $p$ that minimizes the bound
in (<ref>) is $\frac{1}{\sqrt{n}}$, giving at most
$2\sqrt{n}$ expected survivors.  Iterating this process with optimal
$p$ at each step gives a
sequence of at most $n$, $2\sqrt{n}$, $2\sqrt{2\sqrt{n}}$, etc., expected survivors
after each sifter.  The twos are a little annoying, but a
straightforward induction bounds the expected survivors after $i$
rounds by $4⋅n^{2^{-i}}$.  In particular,
we get at most $8$ expected survivors after $\ceil{\lg \lg n}$ rounds.

At this point it makes sense to switch to a fixed $p$ and a different
analysis.  For $p=1/2$, the first process to access $r$ always
survives, and each subsequent process survives with probability at
most $3/4$ (because it leaves if the first process writes and it
reads).  So the number of “excess” processes drops as $(3/4)^i$, and
an additional $\ceil{\log_{4/3} (7/ε)}$ rounds are enough to reduce the
expected number of survivors from $1+7$ to $1+ε$ for any fixed
$ε$.[This argument essentially follows the
proof of <cit.>, which, because of
neglecting to subtract off a $1$ at one point, ends up with $8/ε$
instead of $7/ε$.]

It follows that

An initial set of $n$ processes can be reduced to $1$ with
probability at least $1-ε$
using $O(\log \log n + \log
(1/ε))$ rounds of sifters.

Let $X$ be the number of survivors after $\ceil{\lg \lg n} +
\ceil{\log_{4/3}(7/ε)}$ rounds of sifters, with probabilities tuned
as described above.  We've shown that $\Exp{X} ≤ 1+ε$, so
$\Exp{X-1} ≤ ε$.  Since $X-1 ≥ 0$, from Markov's inequality we
have $\Prob{X ≥ 2} = \Prob{X-1 ≥ 1} ≤ \Exp{X-1}/1 ≤ ε$.

§.§ Test-and-set using sifters

Sifters were initially designed to be used for test-and-set.  For this
purpose, we treat a return value of $⊥$ as “keep going” and anything
else as “leave with value $1$.”  Using $O(\log \log n)$ rounds of
sifters, we can get down to one process that hasn't left with
probability at least $1-\log^{-c} n$ for any fixed constant $c$.
We then need a fall-back TAS to
handle the $\log^{-c} n$ chance that we get more than one such

Alistarh and Aspnes [1] used the RatRace
algorithm of Alistarh  [14] for this purpose.
This is an adaptive randomized test-and-set built from splitters and
two-process consensus objects that runs in $O(\log k)$ expected
time, where $k$ is the number of processes that access the
test-and-set; a sketch of this algorithm is given in
§<ref>.  If we want to avoid appealing to this algorithm, a
somewhat simpler approach is to use an approach similar to the
Lamport's fast-path mutual exclusion algorithm (described in
§<ref>): any process that survives the sifters
tries to rush to a two-process TAS at the top of a tree of
two-processes TASes by winning a splitter, and if it doesn't win the
splitter, it enters at a leaf and pays $O(\log n)$ expected steps.
By setting $\epsilon = 1/\log n$,
the overall expected cost of this final stage is $O(1)$.

This algorithm does not guarantee linearizability.  I might lose a
sifter early on only to have a later process win all the sifters (say,
by writing to each one) and return $0$.  A $\AWWgate$ bit as in
Algorithm <ref> solves this problem.
The full code is given in Algorithm <ref>.

$\AWWgate ≠ ⊥$

$\AWWgate ← \MyId$
$i \leftarrow 1 \dots \ceil{\log \log n} + \ceil{\log_{4/3} (7 \log n)}$
$\min\left(1/2, 2^{1-2^{-i+1}}\right)$
$r_i ← \MyId$

$w ← r_i$
$w ≠ ⊥$

$\Splitter() = \SplitterStop$

Test-and-set in $O(\log \log n)$ expected time

§.§ Consensus using sifters

With some trickery, the sifter mechanism can be adapted to solve
consensus, still in $O(\log \log n)$ expected individual
work [61].  The main difficulty is that a process
can no longer drop out as soon as it knows that it lost: it still
needs to figure out who won, and possible help that winner over the
finish line.

The basic idea is that when a process $p$ loses a sifter to some
other process $q$, $p$ will act like a clone of $q$ from that point
on.  In order to make this work, each process writes down at the start
of the protocol all of the coin-flips it intends to use to decide
whether to read or write at each round of sifting.  Together with its
input, these coin-flips make up the process's persona.  In
analyzing the progress of the sifter, we count surviving personae
(with multiple copies of the same persona counting as one) instead of
surviving processes.

Pseudocode for this algorithm is given in
Algorithm <ref>.  Note that the loop body is
essentially the same as the code in Algorithm <ref>, except
that the random choice is replaced by a lookup in

Let $R = \ceil{\log \log n} + \ceil{\log_{4/3} (7/\epsilon)}$
Let $\ChooseWrite$ be a vector of
random Boolean variables with $\Pr[\ChooseWrite[i] = 1] = p_i$,
where $p_i = 2^{1-2^{-i+1}} (n)^{-2^{-i}}$
for $i \le \ceil{\log \log n}$ and $p_i = 1/2$ for larger $i$.
$\Persona \leftarrow \langle \Input, \ChooseWrite, \MyId\rangle$

$i \leftarrow 1 \dots R$

$\Persona.\ChooseWrite[i] = 1$

$r_i \leftarrow \Persona$

$v \leftarrow r_i$
$v \ne \bot$
$\Persona \leftarrow v$

Sifting conciliator (from [61])

To show that this works, we need to argue that having multiple copies
of a persona around doesn't change the behavior of the sifter.
In each round, we will call the first process with a given persona
$p$ to access $r_i$ the representative of $p$, and argue
that a persona survives round $i$ in this algorithm precisely when its
representative would survive round $i$ in a corresponding test-and-set
sifter with the schedule restricted only to the representatives.

There are three cases:

* The representative of $p$ writes.  Then at least one copy of
$p$ survives.

* The representative of $p$ reads a null value.  Again at
least one copy of $p$ survives.

* The representative of $p$ reads a non-null value.  Then no
copy of $p$ survives: all subsequent reads by processes
carrying $p$ also read a non-null value and discard $p$, and since no process with
$p$ writes, no other process adopts $p$.

From the preceding analysis for test-and-set, we have that after
$O(\log \log n + \log 1/ε)$ rounds with appropriate probabilities of
at most $1+ε$ values survive on average.  This gives a probability of
at most $ε$ of disagreement.  By alternating these conciliators with
adopt-commit objects, we get agreement in $O(\log \log n + \log m /
\log \log m)$ expected time, where $m$ is the number of possible input

I don't think the $O(\log \log n)$ part of this expression is optimal,
but I don't know how to do better.

§.§ A better sifter for test-and-set

A more sophisticated sifter due to Giakkoupis and
Woelfel [148] removes all
but $O(\log n)$ processes, on average, using two operations for each
process.  Iterating this
sifter reduces the expected survivors to $O(1)$ in $O(\log^* n)$
rounds.  A particularly nice feature of the Giakkoupis-Woelfel
algorithm is that (if you don't care about space) it doesn't have any
parameters that require tuning to $n$: this means that exactly the same structure can
be used in each round.  An unfortunate feature is that it's not
possible to guarantee that every process that leaves learns the
identity of a process that stays: this means that it can't adapted
into a consensus protocol using the persona trick described in

Pseudocode is given in Algorithm <ref>.  In this
simplified version, we assume an infinitely long array $A[1\dots]$, so
that we don't need to worry about $n$.  Truncating the array at $\log
n$ also works, but the analysis requires handling the last position as
a special case, which I am too lazy to do here.

Choose $r∈ℤ^{+}$ such that $\Prob{r=i} = 2^{-i}$
$A[r] ← 1$
$A[r+1] = 0$

Giakkoupis-Woelfel sifter [148]

In any execution of Algorithm <ref> with an
oblivious adversary and $n$ processes, at least one process stays,
and the expected number of
processes that stay is $O(\log n)$.

For the first part, observe that any process that picks the
largest value of $r$ among all processes will survive; since the
number of processes is finite, there is at least one such

For the second part, let $X_i$ be the number of survivors with
$r=i$.  Then $\Exp{X_i}$ is bounded by $n⋅2^{-i}$, since no process
survives with $r=i$ without first choosing $r=i$.  But we can also
argue that $\Exp{X_i} ≤ 3$ for any value of $n$, by considering
the sequence of write operations in the execution.

Because the adversary is oblivious, the location of these writes
is uncorrelated with their ordering.  If we assume that the
adversary is trying to maximize the number of survivors, its best
strategy is to allow each process to read immediately after
writing, as delaying this read can only increase the probability
that $A[r+1]$ is nonzero.  So in computing $X_i$, we are counting
the number of writes to $A[i]$ before the first write to $A[i+1]$.
Let's ignore all writes to other registers; then the $j$-th write
to either of $A[i]$ or $A[i+1]$ has a conditional probability of
$2/3$ of landing on $A[i]$ and $1/3$ on $A[i+1]$.  We are thus
looking at a geometric distribution with parameter $1/3$, which
has expectation $3$.

Combining these two bounds gives $\Exp{X_i} ≤ \min(3, 2^{-i})$.
So then

\begin{align*}
\Exp{\mbox{survivors}}
&≤ ∑_{i=1}^{∞} \min(3, n⋅2^{-i}) \\
&= 3 \lg n + O(1),
\end{align*}

because once $n⋅2^{-i}$ drops below $3$, the remaining terms form
a geometric series.

Like square root, logarithm is concave, so Jensen's inequality applies
here as well.  So $O(\log^* n)$ rounds of
Algorithm <ref> reduces us to an expected constant
number of survivors, which can then be fed to RatRace.

With an adaptive adversary, all of the sifter-based test-and-sets fail
badly: in this particular case, an adaptive adversary can sort the
processes in order of increasing write location so that every process
survives.  The best known $n$-process test-and-set for an adaptive
adversary is still a tree of $2$-process randomized test-and-sets, as
in the Afek  [69] algorithm described in
§<ref>.  Whether
$O(\log n)$ expected steps is in fact necessary is still open (as is
the exact complexity of test-and-set with an oblivious adversary).

§ SPACE BOUNDS

A classic result of Fich, Herlihy, and Shavit [119] showed
that $Ω(\sqrt{n})$ registers are needed to solve consensus even under
the very weak requirement of nondeterministic solo
termination, which says that for every reachable configuration
and every process $p$, there exists some continuation of the execution
in which the protocol terminates with only $p$ running.  The best
known upper bound is the trivial bound of $n$—one single-writer register per
process—since any algorithm that uses multi-writer registers can be translated
into one that uses only single-writer registers, and (assuming wide enough registers)
multiple registers of a single process can be combined into one.

For many years,
there was very little progress in closing the gap between these
two bounds.  In 2013, we got a hint that FHS might be tight when
Giakkoupis  [139]
gave a surprising $O(\sqrt{n})$-space algorithm for the closely
related problem of obstruction-free one-shot test-and-set.

But then
Gelashvili [137] showed an $n/20$ space lower
bound for consensus for anonymous processes, and Zhu quickly
followed this with a lower bound for non-anonymous
processes [228], showing that at least $n-1$ registers are
required, using
a clever combination of bivalence and covering arguments.
Around the same time, Giakkoupis  [140]
further improved the space complexity of obstruction-free test-and-set
to $O(\log n)$, using a deterministic obstruction-free implementation
of a sifter.  So the brief coincidence of the $Ω(\sqrt{n})$ lower bound
on consensus and the $O(\sqrt{n})$ upper bound on test-and-set turned
out to be an accident.

For consensus, there is still a gap, but it's a very small gap.  Whether the
actual space needed is $n-1$ or $n$ remains open.

We will start by following the presentation in
<cit.>.  This mostly describes results of the
original paper of Attiya  [17] that defined the
renaming problem and gave a solution for message-passing; however,
it's now more common to treat renaming in the context of
shared-memory, so we will follow Attiya and Welch's translation of
these results to a shared-memory setting.

§ RENAMING

In the renaming problem, we have $n$ processes, each starts
with a name from some huge namespace, and we'd like to assign them
each unique names from a much smaller namespace.  The main application
is allowing us to run algorithms that assume that the processes are
given contiguous numbers, e.g., the various collect or atomic snapshot
algorithms in which each process is assigned a unique register and we
have to read all of the registers.  With renaming, instead of reading a huge pile of registers in order to find the few that are actually used, we can map the processes down to a much smaller set.

Formally, we have a decision problem where each process has input
$x_{i}$ (its original name) and output $y_{i}$, with the requirements:

Termination Every nonfaulty process eventually decides.

Uniqueness If $p_{i} \ne p_{j}$, then $y_{i} \ne y_{j}$.

Anonymity The code executed by any process depends only on its
input $x_{i}$: for any execution of processes $p_{1}\dots p_{n}$ with
inputs $x_{1}\dots x_{n}$, and any permutation $π$ of $[1\dots n]$,
there is a corresponding execution of processes $p_{π(1)}\dots
p_{π(n)}$ with inputs $x_{1}\dots x_{n}$ in which $p_{π(i)}$
performs exactly the same operations as $p_{i}$ and obtains the same
output $y_{i}$.

The last condition is like non-triviality for consensus: it excludes
algorithms where $p_{i}$ just returns $i$ in all executions.  Typically we do not have to do much to prove anonymity other than observing that all processes are running the same code.

We will be considering renaming in a shared-memory system, where we only have atomic registers to work with.

§ PERFORMANCE

Conventions on counting processes:

* $N$ = number of possible original names.

* $n$ = maximum number of processes.

* $k$ = number of processes that actually execute the algorithm.

Ideally, we'd like any performance measures we get to depend on $k$
alone if possible (giving an adaptive algorithm).  Next best
would be something polynomial in $n$ and $k$.  Anything involving $N$ is bad.

We'd also like to minimize the size of the output namespace.  How well
we can do this depends on what assumptions we make.  For deterministic
algorithms using only read-write registers, a lower bound due to
Herlihy and Shavit [161] shows that we can't get fewer
than $2n-1$ names for general $n$.[This lower bound was
further refined by
Castañeda and Rajsbaum [102], who show that $2n-2$
(but no less!) is possible for certain special values of $n$; all of these lower
bounds make extensive use of combinatorial topology, so we won't try
to present them here.]  Our target thus
will be exactly $2n-1$ output names if possible, or $2k-1$ if we are
trying to be adaptive.  For randomized algorithms, it is possible to
strong renamingstrong or
tight renamingtight
renaming, where the size of the namespace is exactly $k$; we'll see
how to do this in §<ref>.

A small note on bounds: There is a lot of variation in the literature
on how bounds on the size of the output namespace are stated.  The
original Herlihy-Shavit lower bound [161] says that there is no general
renaming algorithm that uses $2n$ names for $n+1$
processes; in other
words, any $n$-process algorithm uses at least $2n-1$ names.  Many
subsequent papers discussing lower bounds on the namespace follow the
approach of Herlihy and Shavit and quote lower bounds that are
generally $2$ higher than the minimum number of names needed for $n$
processes.  This requires a certain amount of translation when
comparing these lower bounds with upper bounds, which use the more
natural convention.

§ ORDER-PRESERVING RENAMING

Before we jump into upper bounds, let's do an easy lower bound from
the Attiya  paper [17].  This bound works on a
variant of renaming called
order-preserving renaming, where we require that $y_{i} < y_{j}$
whenever $x_{i} < x_{j}$.  Unfortunately, this requires a very large
output namespace: with $t$ failures, any asynchronous algorithm for
order-preserving renaming requires $2^t(n-t+1)-1$ possible output names.  This lower bound applies regardless of the model, as long as some processes may start after other processes have already been assigned names.

For the wait-free case, we have $t = n-1$, and the bound becomes just
$2^{n}-1$.  This is a simpler case than the general $t$-failure case, but the essential idea is the same: if I've only seen a few of the processes, I need to leave room for the others.

There is no order-preserving renaming algorithm for $n$ processes
using fewer than $2^{n}-1$ names.

By induction on $n$.  For $n=1$, we use $2^{1}-1=1$ names; this is the
base case.  For larger $n$, suppose we use $m$ names, and consider an
execution in which one process $p_{n}$ runs to completion first.  This
consumes one name $y_{n}$ and leaves $k$ names less than $y_{n}$ and
$m-k-1$ names greater than $y_{n}$.  By setting all the inputs $x_{i}$
for $i < n$ either less than $x_{n}$ or greater than $x_{n}$, we can
force the remaining processes to choose from the remaining $k$ or
$m-k-1$ names.  Applying the induction hypothesis, this gives $k ≥
2^{n-1}-1$ and $m-k-1 ≥ 2^{n-1}-1$, so $m = k+(m-k-1)+1 ≥
2(2^{n-1}-1)+1 = 2^{n}-1$.

§ DETERMINISTIC RENAMING

deterministic renaming, we can't use randomization, and may
or may not have any primitives stronger than atomic registers.  With
just atomic registers, we can only solve loose renaming; with
test-and-set, we can solve tight renaming.  In this section, we
describe some basic algorithms for deterministic renaming.

§.§ Wait-free renaming with 2n-1 names

Here we use Algorithm 55 from [67], which is an
adaptation to shared memory of the message-passing renaming algorithm
of [17].  One odd feature of
the algorithm is that, as written, it is not anonymous: processes
communicate using an atomic snapshot object and use their process ids
to select which component of the snapshot array to write to.  But if
we think of the process ids used in the algorithm as the inputs
$x_{i}$ rather than the actual process ids $i$, then everything works.
The version given in Algorithm <ref> makes this substitution explicit, by treating the
original name $i$ as the input.

$s ← 1$

$a[i] ← s$
$\WFRview ← \Snapshot(a)$
$\WFRview[j] = s$ for some $j$
$r ← \card*{ \{ j : \WFRview[j] \ne ⊥ ∧ j ≤ i \} }$
$s ← r$-th positive integer not in $\{ \WFRview[j] : j
\ne i ∧ \WFRview[j] = ⊥ \}$

Wait-free deterministic renaming

The array $a$ holds proposed names for each process (indexed by the
original names), or $⊥$ for processes that have not proposed a name
yet.  If a process proposes a name and finds that no other process has
proposed the same name, it takes it; otherwise it chooses a new name
by first computing its rank $r$ among the active processes and then
choosing the $r$-th smallest name that hasn't been proposed by another
process.  Because the rank is at
most $n$ and there are at most $n-1$ names proposed by the other
processes, this always gives proposed names in the range $[1\dots
2n-1]$.  But it remains to show that the algorithm satisfies uniqueness and termination.

For uniqueness, consider two process with original names $i$ and $j$.
Suppose that $i$ and $j$ both decide on $s$.  Then $i$ sees a view in
which $a[i] = s$ and $a[j] \ne s$, after which it no longer updates
$a[i]$.  Similarly, $j$ sees a view in which $a[j] = s$ and $a[i] \ne
s$, after which it no longer updates $a[j]$.  If $i$'s view is
obtained first, then $j$ can't see $a[i] \ne s$, but the same holds if
$j$'s view is obtained first.  So in either case we get a contradiction, proving uniqueness.

Termination is a bit trickier.  Here we argue that no process can run
forever without picking a name, by showing that if we have a set of
processes that are doing this, the one with smallest original name
eventually picks a name.  More formally, call a process
trying if it runs for infinitely many steps without choosing
a name.  Then in any execution with at least one trying process,
eventually we reach a configuration where all processes have either
finished or are trying.  In some subsequent configuration, all the
processes have written to the $a$ array at least once;
from this point on, the set of non-null positions in $a$—and thus
the rank each process computes for itself—is stable.

Starting from some such stable configuration,
look at the trying process $i$ with the smallest original name,
and suppose it has rank $r$.  Let $F = \{ z_{1} < z_{2} \dots{} \}$ be
the set of “free names” that are not proposed in $a$ by any of the
finished processes.  Observe that no trying process $j \ne i$ ever
proposes a name in $\{ z_{1} \dots{} z_{r} \}$, because any such
process has rank greater than $r$.  This leaves $z_{r}$ open for $i$
to claim, provided the other names in $\{ z_{1} \dots{} z_{r} \}$
eventually become free.  But this will happen, because only trying
processes may have proposed these names (early on in the execution,
when the finished processes hadn't finished yet), and the trying
processes eventually propose new names that are not in this range.  So
eventually process $i$ proposes $z_{r}$, sees no conflict, and finishes, contradicting the assumption that it is trying.

Note that we haven't proved any complexity bounds on this algorithm at
all, but we know that the snapshot alone takes at least $\Omega(N)$
time and space.
Brodksy  [76] cite a paper of Bar-Noy and
Dolev [84]
as giving a shared-memory version of [17] with
complexity $O(n ⋅ 4^n)$; they also give algorithms and pointers to
algorithms with much better complexity.

§.§ Long-lived renaming

long-lived renaming a process can release a name for later
use by other processes (or the same process, if it happens to run
choose-name again).  Now the bound on the number of names needed is
$2k-1$, where $k$ is the maximum number of concurrently active
processes.  Algorithm <ref> can be converted to a long-lived
renaming algorithm by adding the procedure given in
Algorithm <ref>.  This just erases
the process's proposed name, so that some other process can claim it.

$a[i] ← ⊥$

Releasing a name

Here the termination requirement is weakened slightly, to say that
some process always makes progress in .  It may be, however,
that there is some process that never successfully obtains a name,
because it keeps getting stepped on by other processes zipping in and
out of and .

§.§ Renaming without snapshots

Moir and Anderson [187] give a renaming protocol that is
somewhat easier to understand and doesn't require taking snapshots
over huge arrays.  A downside is that the basic version requires
$k(k+1)/2$ names to handle $k$ active processes.

§.§.§ Splitters

The Moir-Anderson renaming protocol uses a network of
splitters, which we last saw providing a fast path for
mutual exclusion in §<ref>.  Each splitter
is a widget, built from a pair of atomic registers, that assigns to
each processes that arrives at it the value ,
, or .
As discussed previously, the useful properties of
splitters are that if at least one process arrives at a splitter, then
(a) at least one process returns or ; and (b) at
least one process returns or ; (c) at most
one process returns ; and (d) any process that runs by
itself returns .

We proved the last two properties in
§<ref>; we'll prove the first two here.
Another way of describing these properties is that of all the
processes that arrive at a splitter, some process doesn't go down and
some process doesn't go right.  By arranging splitters in a grid, this
property guarantees that every row or column that gets at least one
process gets to keep it—which means that with $k$ processes, no
process reaches row $k+1$ or column $k+1$.

Algorithm <ref> gives the implementation of a
splitter (it's identical to Algorithm <ref>, but it will
be convenient to have another copy here).

Implementation of a splitter

If at least one process completes the splitter, at least one process
returns $\SplitterStop$ or $\SplitterRight$.

Suppose no process returns ; then every process sees
in , which means that every process writes
its id to before any process closes the door.  Some
process writes its id last: this process will see its own id in
and return .

If at least one process completes the splitter, at least one process
returns $\SplitterStop$ or $\SplitterDown$.

First observe that if no process ever writes to , then no
process completes the splitter, because the only way a process can
finish the splitter without writing to is if it sees
when it reads (which must have been
written by some other process).  So if at least one process finishes,
at least one process writes to .  Let $p$ be any such
process.  From the code, having written , it has already
passed up the chance to return ; thus it either returns
or .

§.§.§ Splitters in a grid

Now build an $m$-by-$m$ triangular grid of splitters, arranged as rows $0\dots
m-1$ and columns $0\dots m-1$, where a splitter appears in each
position $(r,c)$ with $r+c ≤ m-1$ (see
Figure <ref> for an example; this figure is taken
from [59]).
Assign a distinct name to each of the $\binom{m}{2}$ splitters in this
To obtain a
name, a process starts at $(r,c) = (0,0)$, and repeatedly executes the
splitter at its current position $(r,c)$.  If the splitter returns
, it moves to $(r,c+1)$; if , it moves to
$(r+1,c)$; if , it stops, and returns the name of its
current splitter.  This gives each name to at most one process (by
Lemma <ref>); we also have to show that if at
most $m$ processes enter the grid, every process stops at some

A $6 \times 6$ Moir-Anderson grid

The argument for this is simple.  Suppose some process $p$ leaves the grid
on one of the $2m$ output wires.
Look at the path it takes to get there (see
Figure <ref>, also taken
from [59]).
Each splitter on this
path must handle at least two processes (or $p$ would have stopped at
that splitter, by Lemma <ref>).
So some other process leaves on the other output
wire, either $\SplitterRight$ or $\SplitterDown$.  If we draw a path from each of
these wires that continues $\SplitterRight$ or $\SplitterDown$ to the end of the grid,
then along each of these $m$ disjoint paths either some splitter stops
a process, or some process reaches a final output wire, each of which
is at a distinct splitter.  But this gives $m$ processes in addition
to $p$, for a total of $m+1$ processes.  It follows that:

An $m\times m$ Moir-Anderson grid solves renaming for up to $m$

[Path through a Moir-Anderson grid]Path taken by a single process through a $6 \times 6$
Moir-Anderson grid (heavy path),
and the 6 disjoint paths it spawns (dashed paths).
(From [59].)

The time complexity of the algorithm is $O(m)$: Each process spends at
most 4 operations on each splitter, and no process goes through more
than $2m$ splitters.  In general, any splitter network will take at
least $n$ steps to stop $n$ processes, because the adversary can run
them all together in a horde that drops only one process at each

If we don't know $k$ in advance, we can still guarantee names of size
$O(k^{2})$ by carefully arranging them so that each $k$-by-$k$ subgrid
contains the first $\binom{k}{2}$ names.
This gives an adaptive renaming algorithm (although the namespace size
is pretty high).
We still have to choose our
grid to be large enough for the largest $k$ we might actually
encounter; the resulting space complexity is $O(n^2)$.

With a slightly more clever arrangement of the splitters, it is
possible to reduce the space complexity to
$O(n^{3/2})$ [59].  Whether further reductions
are possible is an open problem.  Note however that linear time
complexity makes splitter networks uncompetitive with much faster
randomized algorithms (as we'll see in
§<ref>), so this may not be a very
important open problem.

§.§ Getting to 2n-1 names in polynomial space

From before, we have an algorithm that will get $2n-1$ names for $n$
processes out of $N$ possible processes when run using $O(N)$ space
(for the enormous snapshots).  To turn this into a bounded-space
algorithm, run Moir-Anderson first to get down to $Θ(k^{2})$
names, then run the previous algorithm (in $Θ(n^{2})$ space)
using these new names as the original names.

Since we didn't prove anything about time complexity of the
humongous-snapshot algorithm, we can't say much about the time
complexity of this combined one.
Moir and Anderson suggest instead
using an $O(Nk^{2})$ algorithm of Borowsky and Gafni to get $O(k^{4})$
time for the combined algorithm.

This is close to the best known: a
later paper by Afek and Merritt [51] holds the current record for
deterministic adaptive renaming into $2k-1$ names at $O(k^2)$
individual steps.  On the lower bound side, it is known that
$\Omega(k)$ is a lower bound on the individual steps of any
renaming protocol with a polynomial output
namespace [15].

§.§ Renaming with test-and-set

Moir and Anderson give a simple renaming algorithm based on
test-and-set that is
strong renamingstrong
($k$ processes are assigned exactly the
names $1 \dots k$),
adaptive (the time complexity to acquire a name is
$O(k)$), and
long-lived renaminglong-lived, which means that a process can
release its name and the name will be available to processes that
arrive later.
In fact, the resulting algorithm gives
renaming!long-lived strong
long-lived strong renaming,
that the set of names in use will always be no larger than the set of
processes that have started to acquire a name and not yet finished
releasing one; this is a little stronger than just saying that the
algorithm is strong and that it is long-lived separately.

The algorithm is simple: we have a line of test-and-set bits $T[1]
\dots T[n]$.  To acquire a name, a process starts at $T[1]$ and
attempts to win each test-and-set until it succeeds; whichever $T[i]$
it wins gives it name $i$.  To release a name, a process releases the

Without the releases, the same mechanism gives
fetch-and-increment [69].  Fetch-and-increment by itself
solves tight renaming (although not long-lived renaming,
since there is no way to release a name).

§ RANDOMIZED RENAMING

With randomization, we can beat both the $2k-1$ lower bound on the
size of the output namespace from [161] and the
$\Omega(k)$ lower bound on individual work
from [15], achieving strong renaming with $O(\log k)$
expected individual work [4].

The basic idea is that we can use randomization for
load balancing, where we avoid the problem of having an army
of processes marching together with only a few peeling off at a time
(as in splitter networks) by having the processes split up based on
random choices.  For example, if each process generates a random name
consisting of $2 \ceil{\lg n}$ bits, then it is reasonably likely that
every process gets a unique name in a namespace of size $O(n^2)$ (we
can't hope for less than $O(n^2)$ because of the birthday
paradox).  But we want all processes to be guaranteed to have unique
names, so we need some more machinery.

We also need the processes to have initial names; if they don't, there
is always some nonzero probability that two identical processes will flip their
coins in exactly the same way and end up with the same name.  This
observation was formalized by Buhrman, Panconesi, Silvestri, and
Vitányi [87].

§.§ Randomized splitters

Attiya  [47]
suggested the use of
randomized splitterrandomized splitters in the
context of another problem
(collect!adaptiveadaptive collect)
that is closely related to renaming.

A randomized splitter is just like a regular splitter, except that if
a process doesn't stop it flips a coin to decide whether to go right
or down.  Randomized splitters are nice because they usually split
better than deterministic splitters: if $k$ processes reach a
randomized splitter, with high probability no more than $k/2 +
O(\sqrt{k \log k})$ will leave on either output wire.

It's not hard to show that a binary tree of these things of
depth $2 \ceil{\lg n}$ stops all but a constant expected number of
processes on average;[The proof is to consider the expected
number of pairs of processes that flip their coins the same way for
all $2 \ceil{\lg n}$ steps.  This is at most $\binom{n}{2} n^{-2} <
1/2$, so on average at most 1 process escapes the tree, giving (by
symmetry) at most a $1/n$ chance that any particular process escapes.
Making the tree deeper can give any polynomial fraction of escapees
while still keeping $O(\log n)$ layers.]
processes that don't stop can be dropped into a backup
renaming algorithm (Moir-Anderson, for example) with only a
constant increase in expected individual work.

Furthermore, the binary tree of randomized splitters is adaptive; if
only $k$ processes show up, we only need $O(\log k)$ levels
levels on average to split them up.
This gives renaming
into a namespace with expected size $O(k^2)$ in $O(\log k)$ expected individual

§.§ Randomized test-and-set plus sampling

Subsequent work by Alistarh  [14]
showed how some of the same ideas
could be used to get strong renaming, where the output namespace has
size exactly $n$ (note this is not adaptive; another result in the same
paper gives adaptive renaming, but it's not strong).
There are two pieces to this result: an implementation of randomized
test-and-set called RatRace, and a sampling procedure for
getting names called ReShuffle.

The RatRaceRatRace protocol implements a randomized test-and-set
with $O(\log k)$ expected individual work.  The essential idea is to
use a tree of randomized splitters to assign names, then have
processes walk back up the same tree attempting to win a $3$-process
randomized test-and-set at each node (there are 3 processes, because in
addition to the winners of each subtree, we may also have a process
that stopped on that node in the renaming step); this test-and-set is
just a very small binary tree of 2-process test-and-sets implemented
using the algorithm of Tromp and Vitányi [223].  A bit is added
at the top as in the test-and-set protocol of
Afek  [37] to get linearizability.

Once we have test-and-set, we could get strong renaming using a linear
array of test-and-sets as suggested by Moir and
Anderson [187], but it's more efficient to use the
randomization to spread the processes out.  In the
protocol, each process chooses a name in the range $[1 \dots n]$
uniformly at random, and attempts to win a test-and-set guarding that
name.  If it doesn't work, it tries again.  Alistarh  show that
this method produces unique names for everybody in $O(n \log^4 n)$
total steps with high probability.  The individual step complexity of
this algorithm, however, is not very good: there is likely to be some
unlucky process that needs $\Omega(n)$ probes (at an expected cost of
$Θ(\log n)$ steps each) to find an empty slot.

§.§ Renaming with sorting networks

A later paper by Alistarh  [4] reduces the
cost of renaming still further, getting $O(\log k)$ expected individual step
complexity for acquiring a name.
The resulting algorithm is both adaptive and strong: with $k$
processes, only names $1$ through $k$ are used.
We'll describe the non-adaptive
version here.

The basic idea is to build a
network!sortingsorting network out of test-and-sets;
the resulting structure, called a
network!renamingrenaming network, routes each
process through a sequence of test-and-sets to a unique output wire.
Unlike a splitter network, a renaming network uses the stronger
properties of test-and-set to guarantee that (once the dust settles)
only the lowest-numbered output wires are chosen; this gives
strong renaming.

§.§.§ Sorting networks

A sorting network is a kind of parallel sorting algorithm that
proceeds in synchronous rounds, where in each round the elements of an
array at certain fixed positions are paired off and swapped if they
are out of order.  The difference between a sorting network and a
standard comparison-based sort is that the choice of which positions
to compare at each step is static, and doesn't depend on the outcome
of previous comparisons; also, the only effect of a comparison is
possibly swapping the two values that were compared.

Sorting networks are drawn as in Figure <ref>.
Each horizontal line or wire corresponds to a position in
the array.  The vertical lines are comparators that compare
two values coming in from the left and swap the larger value to the
bottom.  A network of comparators is a sorting network if the
sequences of output values is always sorted no matter what the order
of values on the inputs is.

A sorting network

The depth!sorting networkdepth of a sorting network
is the maximum number of comparators on any path from an input to an
output.  The width!sorting networkwidth is the number
of wires; equivalently, the number of values the network can sort.
The sorting network in Figure <ref> has depth 3
and width 4.

Explicit constructions of sorting networks with width $n$ and depth
$O(\log^2 n)$ are known [70].  It is
also known that sorting networks with depth $O(\log n)$
exist [48],
but no explicit construction of such a network is

§.§.§ Renaming networks

To turn a sorting network into a renaming network, we replace the
comparators with test-and-set bits, and allow processes to walk
through the network asynchronously.  This is similar to an earlier
mechanism called a
counting network [42], which used certain
special classes of sorting networks as counters, but here any sorting
network works.

Each process starts on a separate input wire, and we maintain the
invariant that at most one process ever traverses a wire.  It follows
that each test-and-set bit is only used by two processes.  The first
process to reach the test-and-set bit is sent out the lower output,
while the second is sent out the upper output.  If we imagine each
process that participates in the protocol as a one and each process
that doesn't as a zero, the test-and-set bit acts as a comparator: if
no processes show up on either input (two zeros), no processes leave
(two zeros again); if processes show up on both inputs (two ones),
processes leave on both (two ones again); and if only one process ever
shows up (a zero and a one), it leaves on the bottom output (zero and
one, sorted).  Because the original sorting network sorts all the ones
to the bottom output wires, the corresponding renaming network sorts
all the processes that arrive to the bottom outputs.  Label these
outputs starting at $1$ at the bottom to get renaming.

Since each test-and-set involves at most two processes, we can carry
them out in $O(1)$ expected register operations using, for example,
the protocol of Tromp and Vitányi [223].  The expected
cost for a process to acquire a name is then $O(\log n)$ (using an
AKS [48]
sorting network).  A more complicated construction in the
Alistarh  paper
shows how to make this adaptive,
giving an expected cost of $O(\log k)$ instead.

The problem with using an AKS network is that the AKS result is
non-constructive: what Ajtai, Komlós, and Szemerédi show is that there
is a particular randomized construction of candidate sorting networks
that succeeds in producing a correct sorting network with nonzero (but
very small) probability.  Other disturbing features of this result are
that we have no efficient way to test candidate sorting networks
(determining if a network of comparators is in fact a sorting network
is co--hard), and the constant in the big-O for AKS is quite
spectacularly huge.  So it probably makes more sense to think of
renaming networks as giving renaming in $O(\log^2 n)$ time, since this
is the most efficient practical sorting network we currently know
about.  This has led to efforts to produce $O(\log k)$-work tight renaming algorithms
that don't depend on AKS.  So far this has not worked out in the
standard shared-memory model, even allowing test-and-sets.[The
closest to this so far is an algorithm of
Berenbrink  [71], who use an extended model
that incorporates an extra primitive called a $τ$-register,
which is basically a collection of $2 \log n$ test-and-set objects
that are restricted so that at most $τ < 2 \log n$ of them can be set
at a time.  Adding this primitive to the model is not entirely cheating, as the
authors make a case that it could be plausibly implemented in
hardware.  But it does mean that we don't know what happens if we
don't have this additional primitive.]

The use of test-and-sets to route processes to particular names is
similar to the line of test-and-sets proposed by Moir and
Anderson [187] as described in
§<ref>.  Some differences
between that protocol and renaming networks is that renaming networks
do not by themselves give fetch-and-increment (although
Alistarh  show how to build fetch-and-increment on top of
renaming networks at a small additional cost),
and renaming networks do not provide any
mechanism for releasing names.
The question of whether it is possible to get cheap
long-lived strong renaming is still open.

§.§ Randomized loose renaming

Loose renaming should be easier than strong renaming, and using
a randomized algorithm it essentially reduces to randomized load
balancing.  A basic approach is to use $2n$ names, and guard each with
a test-and-set; because less than half of the names are taken at any
given time, each process gets a name after $O(1)$ tries and the most
expensive renaming operation over all $n$ processes takes $O(\log n)$
expected steps.

A more sophisticated version of this strategy, which appears
in [16], uses $n(1+ε)$ output names to get
$O(\log \log n)$ maximum steps.  The intuition for why this works is
if $n$ processes independently choose one of $cn$ names uniformly at
random, then the expected number of collisions—pairs of processes
that choose the same name—is $\binom{n}{2}/cn$, or about $n/2c$.
This may seem like only a constant-factor improvement, but if we
instead look at the ratio between the survivors $n/2c$ and the number
of allocated names $cn$, we have now moved from $1/c$ to $1/2c^2$.
The $2$ gives us some room to reduce the number of names in the next
round, to $cn/2$, say, while still keeping a $1/c^2$ ratio of
survivors to names.

So the actual renaming algorithm consists of allocating $cn/2^i$ names
to round $i$, and squaring the ratio of survivors to names in each
rounds.  It only takes $O(\log \log n)$ rounds to knock the ratio of
survivors to names below $1/n$, so at this point it is likely that all
processes will have finished.  At the same time, the sum over all
rounds of the allocated names forms a geometric series, so only $O(n)$
names are needed altogether.

Swept under the carpet here is a lot of careful analysis of the
probabilities.  Unlike what happens with sifters
(see §<ref>), Jensen's inequality goes the wrong way
here, so some additional technical tricks are needed (see the paper
for details).  But the result is that only $O(\log \log n)$ rounds are
to assign every process a name with high probability, which is the
best value currently known.

There is a rather weak lower bound in the Alistarh  paper that
shows that $Ω(\log \log n)$ steps are needed for some process in the
worst case, under the assumption that the renaming algorithm uses only
test-and-set objects and that a process acquires a name as soon as it
wins some test-and-set object.  This does not give a lower bound on
the problem in general, and indeed the renaming-network based
algorithms discussed previously do not have this property.  So the
question of the exact complexity of randomized loose renaming is still

Software transactional memory2011If you are interested in software
transactional memory from a theoretical perspective, there is a
more recent survey on
this material by Attiya [64], available at

transactional memory!software
software transactional memorySoftware transactional memory, or STM for short,
goes back to Shavit and Touitou [220] based on earlier
proposals for hardware support for transactions by Herlihy and
Moss [159].  Recently very popular in programming
language circles.  We'll give a high-level description of the Shavit and Touitou
results; for full details see the actual paper.

We start with the basic idea of a transaction.  In a
transaction, I read a bunch of registers and update their values,
and all of these operations appear to be atomic,
in the sense that the transaction either happens
completely or not at all, and serializes with other transactions as if each occurred instantaneously.  Our goal is to implement this with minimal hardware support, and use it for everything.

Generally we only consider
static transactionstatic transactions
where the set of memory locations accessed is known in advance, as opposed to
dynamic transactiondynamic transactions where it may
vary depending on what we read (for example, maybe we have to follow
pointers through some data structure).  Static transactions are easier
because we can treat them as multi-word read-modify-write.

Implementations are usually non-blocking: some infinite
stream of transactions succeed, but not necessarily yours.  This
excludes the simplest method based on acquiring locks, since we have
to keep going even if a lock-holder crashes, but is weaker than
wait-freedom since we can have starvation.

§ MOTIVATION

Some selling points for software transactional memory:

* We get atomic operations without having to use our brains much.
Unlike hand-coded atomic snapshots, counters, queues, etc., we have a
universal construction that converts any sequential data structure
built on top of ordinary memory into a concurrent data structure.
This is useful since most programmers don't have very big brains.  We
also avoid burdening the programmer with having to remember to lock things.

* We can build large shared data structures with the possibility of concurrent access.  For example, we can implement atomic snapshots so that concurrent updates don't interfere with each other, or an atomic queue where enqueues and dequeues can happen concurrently so long as the queue always has a few elements in it to separate the enqueuers and dequeuers.

* We can execute atomic operations that span multiple data structures,
even if the data structures weren't originally designed to work
together, provided they are all implemented using the STM mechanism.
This is handy in classic database-like settings, as when we
want to take $5 from my bank account and put it in yours.

On the other hand, we now have to deal with the possibility that operations may fail.  There is a price to everything.

§ BASIC APPROACHES

* Locking (not non-blocking).  Acquire either a single lock for
all of memory (doesn't allow much concurrency) or a separate lock for
each memory location accessed.  The second approach can lead to
deadlock if we aren't careful, but we can prove that if every
transaction acquires locks in the same order (e.g., by increasing memory address), then we never get stuck: we can order the processes by the highest lock acquired, and somebody comes out on top.  Note that acquiring locks in increasing order means that I have to know which locks I want before I acquire any of them, which may rule out dynamic transactions.

* Single-pointer compare-and-swap (called ”Herlihy's
method” in [220], because of its earlier use for constructing concurrent data
structures by Herlihy [154]).
All access to the data
structure goes through a pointer in a CAS.  To execute a transaction,
I make my own copy of the data structure, update it, and then attempt
to redirect the pointer.  Advantages: trivial to prove that the
result is linearizable (the pointer swing is an atomic action) and
non-blocking (somebody wins the CAS); also, the method allows dynamic
transactions (since you can do anything you want to your copy).
Disadvantages: There's a high overhead of the many copies,[This
overhead can be reduced in many cases by sharing components, a
subject that has seen much work in the functional programming
literature.  See for
example [198].] and the single-pointer bottleneck limits concurrency even when two transactions use disjoint parts of memory.

* Multiword RMW: This is the approach suggested by Shavit and
Touitou, which most subsequent work follows.  As usually implemented, it only works for static transactions.  The idea is that I write down what registers I plan to update and what I plan to do to them.  I then attempt to acquire all the registers.  If I succeed, I update all the values, store the old values, and go home.  If I fail, it's because somebody else already acquired one of the registers.  Since I need to make sure that somebody makes progress (I may be the only process left alive), I'll help that other process finish its transaction if possible.  Advantages: allows concurrency between disjoint transactions.  Disadvantages: requires implementing multi-word RMW—in particular, requires that any process be able to understand and simulate any other process's transactions.  Subsequent work often simplifies this to implementing multi-word CAS, which is sufficient to do non-blocking multi-word RMW since I can read all the registers I need (without any locking) and then do a CAS to update them (which fails only if somebody else succeeded).

§ IMPLEMENTING MULTI-WORD RMW

We'll give a sketchy description of
Shavit and Touitou's method [220], which
essentially follows the locking approach but allows other processes to
help dead ones so that locks are always released.

The synchronization primitive used is
LL/SC: LL
(load-linked) reads a
register and leaves our id attached to it, SC
(store-conditional) writes a register only
if our id is still attached, and clears any other id's that might also
be attached.  It's easy to build a 1-register CAS (CAS1) out of this,
though Shavit and Touitou exploit some additional power of LL/SC.

§.§ Overlapping LL/SC

The particular trick that gets used in the Shavit-Touitou protocol is
to use two overlapping LL/SC pairs to do a CAS-like update on one
memory location while checking that another memory location hasn't
changed.  The purpose of this is to allow multiple processes to
work on the same transaction (which requires the first CAS to avoid
conflicts with other transactions) while making sure that slow
processes don't cause trouble by trying to complete transactions that
have already finished (the second check).

To see this in action, suppose we have a register $r$ that we want to
do a CAS on, while checking that a second register $\STMstatus$ is
$⊥$ (as opposed to $\STMsuccess$ or $\STMfailure$).  If we execute
the code fragment in Algorithm <ref>, it will
succeed only if nobody writes to $\STMstatus$ between its and and similarly for $r$; if this occurs, then at the time of $\LL(r)$,
we know that $\STMstatus = ⊥$, and we can linearize the write to
$r$ at this time if we restrict all access to $r$ to go through LL/SC.

$\LL(\STMstatus) = ⊥$
$\LL(r) = \DataSty{oldValue}$
$\SC(\STMstatus, ⊥) = \True$
$\SC(r, \DataSty{newValue})$

Overlapping LL/SC

§.§ Representing a transaction

Transactions are represented by records $\STMrec$.  Each such record
consists of a component that describes how far the
transaction has gotten (needed to coordinate cooperating processes), a
component that distinguishes between versions that may
reuse the same space (and that is used to shut down the transaction
when complete), a stable component that indicates when the
initialization is complete, an Op component that describes the RMW to be
performance, an array $\STMaddresses[]$ of pointers to the arguments
to the RMW, and an array $\STMoldValues[]$ of old values at these
addresses (for the R part of the RMW).
These are all initialized by the initiator of the transaction, who
will be the only process working on the transaction until it starts
acquiring locks.

§.§ Executing a transaction

Here we give an overview of a transaction execution:

* Initialize the record for the
transaction.  (Only the initiator does this.)

* Attempt to acquire ownership of registers in
$\STMaddresses[]$.  See the AcquireOwnerships code in the
paper for details.  The essential idea is that we want to set the
field $\STMowner[r]$ for each memory location $r$ that we need to
lock; this is done using an overlapping LL/SC as described above so
that we only set $\STMowner[r]$ if (a) $r$ is currently unowned, and
(b) nothing has happened to $\STMrec.\STMstatus$ or
$\STMrec.\STMversion$.  Ownership is acquired in order of increasing
memory address; if we fail to acquire ownership for some $r$, our
transaction fails.  In case of failure, we set $\STMrec.\STMstatus$
to and release all the locks we've acquired (checking
$\STMrec.\STMversion$ in the middle of each LL/SC so we don't release
locks for a later version using the same record).  If we are the
initiator of this transaction, we will also go on to attempt to
complete the transaction that got in our way.

* Do a on $\STMrec.\STMstatus$ to see if
AcquireOwnerships succeeded.  If
so, update the memory, store the old results in , and release
the ownerships.  If it failed, release ownership and help the next
transaction as described above.

Note that only an initiator helps; this avoids a long chain of
helping and limits the cost of each attempted transaction to the cost
of doing two full transactions, while (as shown below) still allowing
some transaction to finish.

§.§ Proof of linearizability

Intuition is:

* Linearizability follows from the linearizability of the locking protocol: acquiring ownership is equivalent to grabbing a lock, and updates occur only when all registers are locked.

* Complications come from (a) two or more processes trying to
complete the same transaction and (b) some process trying to complete
an old transaction that has already terminated.  For the first part
we just make sure that the processes don't interfere with each other,
e.g. I am happy when trying to acquire a location if somebody else
acquires it for the same transaction.  For the second part we have to
check $\STMrec.\STMstatus$ and $\STMrec.\STMversion$ before doing just about anything.
See the pseudocode in the paper for details on how this is done.

§.§ Proof of non-blockingness

To show that the protocol is non-blocking we must show that if an
unbounded number of transactions are attempted, one eventually
succeeds.  First observe that in order to fail, a transaction must be
blocked by another transaction that acquired ownership of a
higher-address location than it did; eventually we run out of
higher-address locations, so there is some transaction that doesn't
fail.  Of course, this transaction may not succeed (e.g., if its
initiator dies), but either (a) it blocks some other transaction, and
that transaction's initiator will complete it or die trying, or (b) it
blocks no future transactions.  In the second case we can repeat the
argument for the $n-1$ surviving processes to show that some of them complete transactions, ignoring the stalled transaction from case (b).

§ IMPROVEMENTS

One downside of the Shavit and Touitou protocol is that it uses LL/SC
very aggressively (e.g., with overlapping LL/SC operations) and uses
non-trivial (though bounded, if you ignore the ever-increasing version
numbers) amounts of extra space.  Subsequent work has aimed at
knocking these down; for example a paper by Harris, Fraser, and
Pratt [155] builds multi-register CAS out of
single-register CAS with $O(1)$ extra bits per register.  The proof of
these later results can be quite involved; Harris , for example, base their algorithm on an implementation of 2-register CAS whose correctness has been verified only by machine (which may be a plus in some views).

§ LIMITATIONS

There has been a lot of practical work on STM designed to reduce
overhead on real hardware, but there's still a fair bit of overhead.
On the theory side, a lower bound of Attiya, Hillel, and
Milani [40] shows that any STM system that guarantees
non-interference between non-overlapping RMW transactions has the
undesirable property of making read-only transactions as expensive as
RMW transactions: this
conflicts with the stated goals of many practical STM implementations,
where it is assumed that most transactions will be read-only (and
hopefully cheap).  So there is quite a bit of continuing research on
finding the right trade-offs.

Obstruction-freedom2011In particular:
§<ref> has not
been updated to include some more recent
results [26, 139];
and §<ref> mostly follows the conference
version [120] of the Ellen-Hendler-Shavit paper and omits
stronger results from the journal version [115].

The gold standard for shared-memory objects is wait-freewait-freedom:
I can finish my operation in a bounded number of steps no matter what
anybody else does.  Like the gold standard in real life, this can be
overly constraining.  So researchers have developed several weaker progress guarantees that are nonetheless useful.  The main ones are:

Lock-freedom An implementation is lock-free if
infinitely many operations finish in any infinite execution.  In
simpler terms, somebody always makes progress, but maybe not you.
(Also called non-blocking.)

Obstruction-freedom An implementation is
obstruction-free if, starting from any reachable
configuration, any process can finish in a bounded number of steps if
all of the other processes stop.  This definition was proposed in
2003 by Herlihy, Luchangco, and Moir [158].  In lower
bounds (e.g., the Jayanti-Tan-Toueg bound described in
Chapter <ref>) essentially the same property is often called solo-terminating.

Both of these properties exclude traditional lock-based algorithms,
where some process grabs a lock, updates the data structure, and then
release the lock; if this process halts, no more operations finish.
Both properties are also weaker than wait-freedom.  It is not hard to
show that lock-freedom is a stronger condition that
obstruction-freedom: given a lock-free implementation, if we can keep
some single process running forever in isolation, we get an infinite
execution with only finitely many completed operations.  So we have a
hierarchy: wait-free $>$ lock-free $>$ obstruction-free $>$ locking.

§ WHY BUILD OBSTRUCTION-FREE ALGORITHMS?

The pitch is similar to the pitch for building locking algorithms: an
obstruction-free algorithm might be simpler to design, implement, and
reason about than a more sophisticated algorithm with stronger
properties.  Unlike locking algorithms, an obstruction-free algorithm
won't fail because some process dies holding the lock; instead, it
fails if more than one process runs the algorithm at the same time.
This possibility may be something we can avoid by building a
contention manager, a high-level protocol that detects contention and delays some processes to avoid it (say, using randomized exponential back-off).

§ EXAMPLES

§.§ Lock-free implementations

Pretty much anything built using compare-and-swap or LL/SC ends up being lock-free.  A simple example would be a counter, where an increment operation does
$x ← \LL(C)$
$\SC(C, x+1)$

This is lock-free (the only way to prevent a store-conditional from succeeding is if some other store-conditional succeeds, giving infinitely many successful increments) but not wait-free (I can starve).  It's also obstruction-free, but since it's already lock-free we don't care about that.

§.§ Double-collect snapshots

Similarly, suppose we are doing atomic snapshots.  We know that there exist wait-free implementations of atomic snapshots, but they are subtle and confusing.  So we want to do something simpler, and hope that we at least get obstruction-freedom.

If we do double-collects, that is, we have updates just write to a register and have snapshots repeatedly collect until they get two collects in a row with the same values, then any snapshot that finishes is correct (assuming no updaters ever write the same value twice, which we can enforce with nonces).  This isn't wait-free, because we can keep a snapshot going forever by doing a lot of updates.  It is lock-free, because we have to keep doing updates to make this happen.

We can make this merely obstruction-free if we work hard (there is no
reason to do this, but it illustrates the difference between
lock-freedom—good—and obstruction-freedom—not so good).  Suppose
that every process keeps a count of how many collects it has done in a
register that is included in other process's collects (but not its
own).  Then two concurrent scans can stall each other forever (the
implementation is not lock-free), but if only one is running it
completes two collects in $O(n)$ operations without seeing any changes (it is obstruction-free).

§.§ Software transactional memory

Similar things happen with software transactional memory (see
Chapter <ref>).  Suppose that I have an implementation of multiword compare-and-swap, and I want to carry out a transaction.  I read all the values I need, then execute an MCAS operation that only updates if these values have not changed.  The resulting algorithm is lock-free (if my transaction fails, it's because some update succeeded).  If however I am not very clever and allow some values to get written outside of transactions, then I might only be obstruction-free.

§.§ Obstruction-free test-and-set

Algorithm <ref> gives an implementation of
$2$-process test-and-set from atomic registers that is
obstruction-free; this demonstrates that obstruction-freedom lets us
evade the wait-free impossibility results implied by the consensus
hierarchy ([153], discussed in
Chapter <ref>).

The basic idea
goes back to the racing counters technique used in consensus
protocols starting with Chor, Israeli, and Li [96], and
there is some similarity to a classic randomized wait-free
test-and-set due to Tromp
and Vitányi [223].  Each process keeps a position $x$ in
memory that it also stores from time to time in its register $a[i]$.
If a process gets $2$ steps ahead of the other process (as observed by
comparing $x$ to $a[i-1]$, it wins the test-and-set; if a process
falls one or more steps behind, it (eventually) loses.  To keep space down and
guarantee termination in bounded time, all values are tracked modulo

$x ← 0$

$δ ← x - a[1-i]$
$δ = 2 \pmod{5}$

$δ = -1 \pmod{5}$

$x ← (x+1) \bmod{5}$
$a[i] ← x$

Obstruction-free $2$-process test-and-set

Why this works: observe that whenever a process computes $δ$, $x$
is equal to $a[i]$; so $δ$ is always an instantaneous snapshot of
$a[i] - a[1-i]$.  If I observe $δ = 2$ and return $0$, your next
read will either show you $δ = -2$ or $δ = -1$ (depending on
whether you increment $a[1-i]$ after my read).  In the latter case,
you return $1$ immediately; in the former, you return after one more
increment (and more importantly, you can't return $0$).
Alternatively, if I ever observe $δ = -1$, your next read will
show you either $δ = 1$ or $δ = 2$; in either case, you will
eventually return $0$.
(We chose $5$ as a modulus because this is the smallest value that
makes the cases $δ = 2$ and $δ = -2$ distinguishable.)

We can even show that this is linearizable, by considering a solo
execution in which the lone process takes two steps and returns $0$
(with two processes, solo executions are the only interesting case for linearizability).

However, Algorithm <ref> is not
wait-free or even lock-free: if both processes run
in lockstep, they will see $δ = 0$ forever.  But it is
obstruction-free.  If I run by myself, then whatever value of $δ$
I start with, I will see $-1$ or $2$ after at most $6$
operations.[The worst case is where an increment by my fellow
process leaves $δ = -1$ just before
my increment.]

This gives an
complexity!obstruction-free step
step complexity!obstruction-free
obstruction-free step complexity of $6$, where the
obstruction-free step complexity is defined as the maximum number of
operations any process can take after all other processes stop.
Note that our usual wait-free measures of step complexity don't make a
lot of sense for obstruction-free algorithms, as we can expect a
sufficiently cruel adversary to be able to run them up to whatever
value he likes.

Building a tree of these objects as in
§<ref> gives
$n$-process test-and-set with obstruction-free step complexity
$O(\log n)$.

§.§ An obstruction-free deque

(We probably aren't going to do this in class.)

So far we don't have any good examples of why we would want to be
obstruction-free if our algorithm is based on CAS.  So let's describe
the case Herlihy  suggested.