both $<_{T}$ and the timestamp ordering (with writes before reads when timestamps are equal).  To make this work we have to show (a) that these two orderings are in fact consistent, and (b) that the resulting ordering produces values consistent with an atomic register: in particular, that each read returns the value of the last preceding write.

Part (b) is easy: since timestamps only increase in response to
writes, each write is followed by precisely those reads with the same
timestamp, which are precisely those that returned the value written.

For part (a), suppose that $π_1 <_{T} π_2$.  The first case is
when $π_2$ is a read.  Then before the end of $π_1$, a set $S$ of
more than $n/2$ processes send the $π_1$ process an $\Ack(v1,t_1)$
message.  Since local timestamps only increase, from this point on any
$\Ack(v_2,t_2,u)$ message sent by a process in $S$ has $t_2 ≥ t_1$.
Let $S'$ be the set of processes sending $\Ack(v_2,t_2,u)$ messages
processed by $π_2$.  Since $\card*{S} > n/2$ and $\card*{S'} > n/2$,
we have $S\cap S'$ is nonempty and so $S'$ includes a process that
sent $\Ack(v_2,t_2)$ with $t_2 ≥ t_1$.  So $π_2$ is serialized
after $π_1$.  The second case is when $π_2$ is a write; but then
$π_1$ returns a timestamp that precedes the writer's increment in
$π_2,$ and so again is serialized first.

§ PROOF THAT F < N/2 IS NECESSARY

This is pretty much the standard partition argument that $f < n/2$ is
necessary to do anything useful in a message-passing system.  Split
the processes into two sets $S$ and $S'$ of size $n/2$ each.  Suppose
the writer is in $S$.  Consider an execution where the writer does a
write operation, but all messages between $S$ and $S'$ are delayed.
Since the writer can't tell if the $S'$ processes are slow or dead, it
eventually returns.  Now let some reader in $S'$ attempt to read the
simulated register, again delaying all messages between $S$ and $S'$;
now the reader is forced to return some value without knowing whether
the $S$ processes are slow or dead.  If the reader doesn't return the
value written, we lose.  If by some miracle it does, then we lose in
the execution where the write didn't happen and all the processes in
$S$ really were dead.

§ MULTIPLE WRITERS

So far we have assumed a single writer.  The main advantage of this
approach is that we don't have to do much to manage timestamps: the
single writer can just keep track of its own.  With multiple writers
we can use essentially the same algorithm, but each write needs to
perform an initial round of gathering timestamps so that it can pick a
new timestamp bigger than those that have come before.  We also extend
the timestamps to be of the form $\Tuple{\ABDcount, \Id}$, lexicographically ordered, so that two timestamps with the same count field are ordered by process id.  The modified write algorithm is:

* Send $\Read(u)$ to all processes and wait to receive acknowledgments from a majority of the processes.

* Set my timestamp to  $t = (\max_q \ABDcount_q + 1, \Id)$ where
the max is taken over all processes $q$ that sent me an
acknowledgment.  Note that this is a two-field timestamp that is
compared lexicographically, with the field used only to prevent duplicate timestamps.

* Send $\Write(v,t)$ to all processes, and wait for a response
$\Ack(v,t)$ from a majority of processes.

This increases the cost of a write by a constant factor, but in the
end we still have only a linear number of messages.  The proof of
linearizability is essentially the same as for the single-writer
algorithm, except now we must consider the case of two write
operations by different processes.  Here we have that if $π_1 <_{T}
π_2$, then $π_1$ gets acknowledgments of its write with timestamp
$t_1$ from a majority of processes before $π_2$ starts its initial
phase to compute .
Since $π_2$ waits for acknowledgments from a majority of
processes as well, these majorities overlap, so $π_2$'s timestamp
$t_2$ must exceed $t_1$.  So the linearization ordering previously defined still works.

§ OTHER OPERATIONS

The basic ABD framework can be extended to support other operations.

One such operation is a collect [219],
where we read $n$ registers
in parallel with no guarantee that they are read at the same time.
This can trivially be implemented by running $n$ copies of ABD in
parallel, and can be implemented with the same time and message complexity as
ABD for a single register by combining the messages from the parallel
executions into single (possibly very large) messages.

Mutual exclusion2020

For full details see <cit.> or <cit.>.

§ THE PROBLEM

The goal is to share some critical resource between processes without
more than one using it at a time—this is the fundamental
problem in time-sharing systems.

The solution is to only allow access while in a specially-marked block
of code called a critical section, and only allow one process at a time to be in a critical section.

A mutual exclusion protocol guarantees this, usually in an
asynchronous shared-memory model.

Formally: We want a process to cycle between states trying (trying to get into critical section), critical (in critical section), exiting (cleaning up so that other processes can enter their critical sections), and remainder (everything else—essentially just going about its non-critical business).  Only in the trying and exiting states does the process run the mutual exclusion protocol to decide when to switch to the next state; in the critical or remainder states it switches to the next state on its own.

The ultimate payoff is that mutual exclusion solves for
systems without failures what consensus solves for systems with
failures: if the only way to update a data structure is to hold a lock
on it, we are guaranteed to get a nice clean sequence of
atomic-looking updates.  Of course, once we allow failures back in,
mutex becomes less useful, as our faulty processes start crashing
without releasing their locks, and with the data structure in some
broken, half-updated state.[In principle, if we can detect
that a process has failed, we can work around this problem by
allowing some other process to bypass the lock and clean up.  This
may require that the original process leaves behind notes about
what it was trying to do, or perhaps copies the data it is going
to modify somewhere else before modifying it.  But even this doesn't
work if some zombie process can suddenly lurch to life and scribble its ancient
out-of-date values all over our shiny modern data structure.]

§ GOALS

(See also <cit.>, <cit.>.)

Core mutual exclusion requirements:

Mutual exclusion mutual exclusion At most one process is in the critical state at a time.

No deadlock (progress) deadlockprogress
If there is at least one process in a trying state, then eventually some process enters a critical state; similarly for exiting and remainder states.

Note that the protocol is not required to guarantee that processes leave the critical or remainder state, but we generally have to insist that the processes at least leave the critical state on their own to make progress.

An additional useful property (not satisfied by all mutual exclusion
protocols; see <cit.>:

No lockout lockout(lockout-freedom): If there is a particular process in a trying or exiting state, that process eventually leaves that state.  This means that I don't starve because somebody else keeps jumping past me and seizing the critical resource before I can.

Stronger starvation guarantees include explicit time bounds (how
many rounds can go by before I get in) or bounded bypass
(nobody gets in more than $k$ times before I do). Each of these imply
lockout-freedom assuming no deadlock.

§ MUTUAL EXCLUSION USING STRONG PRIMITIVES

See <cit.> or <cit.>.  The idea is
that we will use some sort of read-modify-write register, where the RMW operation computes a new value based on the old value of the register and writes it back as a single atomic operation, usually returning the old value to the caller as well.

§.§ Test and set

A test-and-set operation does the following sequence of actions atomically:
$\TASoldValue ← \Read(\TASbit)$
$\Write(\TASbit, 1)$

Typically there is also a second reset operation for setting
the bit back to zero.  For some implementations, this reset operation
may only be used safely by the last process to get $0$ from the
test-and-set bit.

Because a test-and-set operation is atomic, if two processes both try to perform test-and-set on the same bit, only one of them will see a return value of 0.  This is not true if each process simply executes the above code on a stock atomic register: there is an execution in which both processes read 0, then both write 1, then both return 0 to whatever called the non-atomic test-and-set subroutine.

Test-and-set provides a trivial implementation of mutual exclusion,
shown in Algorithm <ref>.

$\TestAndSet(\MTlock) = 1$nothing
(do critical section stuff)
(do remainder stuff)

Mutual exclusion using test-and-set

It is easy to see that this code provides mutual exclusion, as once
one process gets a 0 out of , no other can escape the inner
while loop until that process calls the operation in its
exiting state.  It also provides progress (assuming the lock is
initially set to 0); the only part of the code that is not
straight-line code (which gets executed eventually by the fairness
condition) is the inner loop, and if is 0, some process
escapes it, while if is 1, some process is in the region
between the call and the call, and so it eventually
gets to and lets the next process in (or itself, if it is very fast).

The algorithm does not provide lockout-freedom: nothing prevents a single fast process from scooping up the lock bit every time it goes through the outer loop, while the other processes ineffectually grab at it just after it is taken away.  Lockout-freedom requires a more sophisticated turn-taking strategy.

§.§ A lockout-free algorithm using an atomic queue

Basic idea: In the trying phase, each process enqueues itself on the
end of a shared queue (assumed to be an atomic operation).  When a
process comes to the head of the queue, it enters the critical
section, and when exiting it dequeues itself.  So the code would look
something like Algorithm <ref>.

Note that this requires a queue that supports a operation.
Not all implementations of queues have this property.

$\Enq(Q, \MyId)$
$\MThead(Q) \ne \MyId$nothing
(do critical section stuff)
(do remainder stuff)

Mutual exclusion using a queue

Here the proof of mutual exclusion is that only the process whose id
is at the head of the queue can enter its critical section.  Formally,
we maintain an invariant that any process whose program counter is
between the inner while loop and the call to $\Deq(Q)$ must be
at the head of the queue; this invariant is easy to show because a
process can't leave the while loop unless the test fails (i.e., it is
already at the head of the queue), no operation changes the
head value (if the queue is nonempty), and the operation (which does change the head value) can only be executed by a process already at the head (from the invariant).

Deadlock-freedom follows from proving a similar invariant that every element of the queue is the id of some process in the trying, critical, or exiting states, so eventually the process at the head of the queue passes the inner loop, executes its critical section, and dequeues its id.

Lockout-freedom follows from the fact that once a process is at
position $k$ in the queue, every execution of a critical section
reduces its position by $1$; when it reaches the front of the queue (after some finite number of critical sections), it gets the critical section itself.
Alternatively, we can argue lockout-freedom by showing bounded bypass: once I am in the queue, no process
can execute two critical sections before I do, because once it leaves
its first critical section, it enqueues behind me.

§.§.§ Reducing space complexity

Following <cit.>, we can give an implementation of this algorithm using a single read-modify-write (RMW) register instead of a queue; this drastically reduces the (shared) space needed by the algorithm.  The reason this works is because we don't really need to keep track of the position of each process in the queue itself; instead, we can hand out numerical tickets to each process and have the process take responsibility for remembering where its place in line is.

The RMW register has two fields, and , both initially
0.  Incrementing last simulates an enqueue, while incrementing
simulates a dequeue.  The trick is that instead of testing if
it is at the head of the queue, a process simply remembers the value
of the field when it “enqueued” itself, and waits for the
field to equal it.

Algorithm <ref> shows the code from
Algorithm <ref> rewritten to use this technique.  The way to
read the operations is that the argument specifies the
variable to update and the second specifies an expression for
computing the new value.  Each operation returns the old state of the object, before the update.

$\MTposition ←
\MTrmw(V, \langle V.\MTfirst, V.\MTlast+1 \rangle)$

$\MTrmw(V,V).\MTfirst \ne \MTposition.\MTlast$
(do critical section stuff)
$\MTrmw(V, \langle V.\MTfirst+1, V.\MTlast \rangle)$
(do remainder stuff)

Mutual exclusion using read-modify-write

§ MUTUAL EXCLUSION USING ONLY ATOMIC REGISTERS

While mutual exclusion is easier using powerful primitives, we can
also solve the problem using only registers.

§.§ Peterson's algorithm

Algorithm <ref> shows Peterson's lockout-free
mutual exclusion protocol for two
processes $p_{0}$ and $p_{1}$ [201] (see also
<cit.> or <cit.>).  It uses only atomic registers.

, initially arbitrary

$\MTpresent[i]$ for $i\in\{0,1\}$, initially $0$

Code for process $i$:

$\MTpresent[i] ← 1$
$\MTwaiting ← i$

$\MTpresent[¬ i] = 0$

$\MTwaiting \ne i$

(do critical section stuff)
$\MTpresent[i] = 0$
(do remainder stuff)

Peterson's mutual exclusion algorithm for two processes

This uses three bits to communicate: $\MTpresent[0]$ and
$\MTpresent[1]$ indicate which of $p_0$ and $p_1$ are participating,
and $\MTwaiting$ enforces turn-taking.
The protocol requires that $\MTwaiting$ be multi-writer, but it's
OK for $\MTpresent[0]$ and $\MTpresent[1]$ to be single-writer.

In the description of the protocol, we write Lines <ref>
and <ref>
as two separate lines because they
include two separate read operations, and the order of these reads is

§.§.§ Correctness of Peterson's protocol

Intuitively, let's consider all the different ways that the entry code
of the two processes could interact.  There are basically two things
that each process does: it sets its own $\MTpresent$ variable in
Line <ref> and grabs the $\MTwaiting$ variable in
Line <ref>.  Here's a typical case where one process gets in first:

* $p_0$ sets $\MTpresent[0] ← 1$

* $p_0$ sets $\MTwaiting ← 0$

* $p_0$ reads $\MTpresent[1] = 0$ and enters critical section

* $p_1$ sets $\MTpresent[1] ← 1$

* $p_1$ sets $\MTwaiting ← 1$

* $p_1$ reads $\MTpresent[0] = 1$ and $\MTwaiting = 1$ and loops

* $p_0$ sets $\MTpresent[0] ← 0$

* $p_1$ reads $\MTpresent[0] = 0$ and enters critical section

The idea is that if I see a $0$ in your $\MTpresent$ variable, I know that you aren't playing, and can just go in.

Here's a more interleaved execution where the waiting variable decides the winner:

* $p_0$ sets $\MTpresent[0] ← 1$

* $p_0$ sets $\MTwaiting ← 0$

* $p_1$ sets $\MTpresent[1] ← 1$

* $p_1$ sets $\MTwaiting ← 1$

* $p_0$ reads $\MTpresent[1] = 1$

* $p_1$ reads $\MTpresent[0] = 1$

* $p_0$ reads $\MTwaiting = 1$ and enters critical section

* $p_1$ reads $\MTpresent[0] = 1$ and $\MTwaiting = 1$ and loops

* $p_0$ sets $\MTpresent[0] ← 0$

* $p_1$ reads $\MTpresent[0] = 0$ and enters critical section

Note that it's the process that set the variable last (and thus sees its own value) that stalls.  This is necessary because the earlier process might long since have entered the critical section.

Sadly, examples are not proofs, so to show that this works in general,
we need to formally verify each of mutual exclusion and
lockout-freedom.  Mutual exclusion is a safety property, so we expect
to prove it using invariants.  The proof
in [186] is based on translating the pseudocode directly
into automata (including explicit program counter variables); we'll do
essentially the same proof but without doing the full translation to
automata.  Below, we write that $p_{i}$ is at line $k$ if it the
operation in line $k$ is enabled but has not occurred yet.

If $\MTpresent[i] = 0$, then $p_{i}$ is at
Line <ref>
or <ref>.

Immediate from the code.

If $p_{i}$ is at Line <ref>,
$p_{¬{}i}$ is at Line <ref>,
or <ref>,
then $\MTwaiting = ¬{}i$.

We'll do the case $i = 0$; the other case is symmetric.  The proof is
by induction on the schedule.  We need to check that any event that
makes the left-hand side of the invariant true or the right-hand side false also makes the whole invariant true.  The relevant events are:

* Transitions by $p_{0}$ from
Line <ref> to
Line <ref>.  These occur only if
$\MTpresent[1] = 0$, implying $p_{1}$ is at Line
Line <ref>
or <ref> by
Lemma <ref>.
In this case the second part of the left-hand side is false.

* Transitions by $p_{0}$ from
Line <ref> to
Line <ref>.  These occur only if
$\MTwaiting \ne 0$, so the right-hand side is true.

* Transitions by $p_{1}$ from
Line <ref> to
Line <ref>.  These
set $\MTwaiting$ to $1$, making the right-hand side true.

* Transitions that set $\MTwaiting$ to $0$.  These are
transitions by $p_{0}$ from Line <ref> to
Line <ref>, making the left-hand side false.

We can now read mutual exclusion directly off of
Lemma <ref>: if both $p_{0}$ and
$p_{1}$ are at Line <ref>,
then we get $\MTwaiting = 1$ and $\MTwaiting = 0$, a contradiction.

To show progress, observe that the only place where both processes can
get stuck forever is in the loop at
Lines <ref>
and <ref>.  But then $\MTwaiting$ isn't
changing, and so some process $i$ reads $\MTwaiting = ¬{}i$ and
leaves.  To show lockout-freedom, observe that if $p_0$ is stuck in
the loop while $p_1$ enters the critical section, then after $p_1$
leaves it sets $\MTpresent[1]$ to $0$ in
Line <ref> (which lets $p_0$ in if
$p_0$ reads $\MTpresent[1]$ in time), but even if it then sets
$\MTpresent[1]$ back to $1$ in Line <ref>,
it still sets to $1$ in
Line <ref>, which lets $p_0$ into the
critical section.  With some more tinkering this argument shows that
$p_1$ enters the critical section at most twice while $p_0$ is in the
trying state, giving $2$-bounded bypass; see
<cit.>.  With even more tinkering we get a
constant time bound on the waiting time for process $i$ to enter the
critical section, assuming the other process never spends more than
$O(1)$ time inside the critical section.

§.§.§ Generalization to n processes

(See also <cit.>.)

The easiest way to generalize Peterson's two-process algorithm to $n$
processes is to organize a tournament in the form of log-depth binary
tree; this method was invented by Peterson and
Fischer [203].  At each node of the tree, the roles of
the two processes are taken by the winners of the subtrees, i.e., the
processes who have entered their critical sections in the two-process
algorithms corresponding to the child nodes.  The winner of the
tournament as a whole enters the real critical section, and afterwards
walks back down the tree unlocking all the nodes it won in reverse
order.  It's easy to see that this satisfies mutual exclusion, and not
much harder to show that it satisfies lockout-freedom—in the latter
case, the essential idea is that if a winner at some node reaches the
root infinitely often, then lockout-freedom at that node means that a
winner of each child node reaches the root infinitely often.

The most natural way to implement the nodes is to have $\MTpresent[0]$
and $\MTpresent[1]$ at each node be multi-writer variables that can be
written to by any process in the appropriate subtree.  Because the
variables don't do much, we can also implement them as the
OR of many single-writer variables (this is what is done in
<cit.>), but there is no immediate payoff to doing this since the waiting variables are still multi-writer.

Nice properties of this algorithm are that it uses only bits and that
it's very fast: $O(\log n)$ time in the absence of contention.

§.§ Fast mutual exclusion

With a bit of extra work, we can reduce the no-contention cost of
mutual exclusion to $O(1)$, while keeping whatever performance we
previously had in the high-contention case.  The trick (due to
Lamport [178]) is to put an object at the entrance to the
protocol that diverts a solo process onto a “fast path” that lets it
bypass the $n$-process mutex that everybody else ends up on.

Our presentation mostly follows [67][4.4.5], which uses the
splitter abstraction of
Moir and Anderson [187] to separate out the mechanism for
diverting a lone process.[Moir and Anderson call these things
one-time building blocks, but the name splitter has become standard in subsequent work.]  Code for a splitter is given in
Algorithm <ref>.

Implementation of a splitter

A splitter assigns to each processes that arrives at it the value
, , or .
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 .
The first two properties will be useful when we consider
the problem of renaming in Chapter <ref>;
we will prove them there.
The last two properties are what we want for mutual exclusion.

The names of the variables $\SplitterRace$ and $\SplitterDoor$ follow
the presentation in <cit.>;
Moir and Anderson [187], following Lamport [178], call these $X$ and $Y$.  As in [187],
we separate out the and
outcomes—even though they are equivalent for
mutex—because we will need them later for other applications.

The intuition behind Algorithm <ref> is that setting
$\SplitterClosed$ closes the door to new entrants, and the last entrant to write
its id to
wins (it's a slow race),
assuming nobody else writes and messes things up.  The added cost
of the splitter is always $O(1)$, since there are no loops.

To reset the splitter, write to .  This
allows new processes to enter the splitter and possibly return

After each time that is set to ,
at most one process running Algorithm <ref> returns $\SplitterStop$.

To simplify the argument, we assume that each process calls
$\Splitter$ at most once.

Let $t$ be some time at which $\SplitterDoor$ is set to
$\SplitterOpen$ ($-\infty$ in the case of the initial value).  Let
$S_t$ be the set of processes that read $\SplitterOpen$ from
$\SplitterDoor$ after time $t$ and before the next time at which some
process writes $\SplitterClosed$ to $\SplitterDoor$, and that later
return $\SplitterStop$ by reaching Line <ref>.

Then every process in $S_t$ reads $\SplitterDoor$ before any process
in $S_t$ writes $\SplitterDoor$.  It follows that every process in
$S_t$ writes $\SplitterRace$ before any process in $S_t$ reads
$\SplitterRace$.  If some process $p$ is not the last process
in $S_t$
to write $\SplitterRace$, it will not see its own id, and will not
return .  But only one process can be the last process in
$S_t$ to
write $\SplitterRace$.[It's worth noting that this last process still might not
return , because some later process—not in
$S_t$—might overwrite $\SplitterRace$.  This can happen even if nobody
ever resets the splitter.]

If a process runs Algorithm <ref> by itself starting from
a configuration in which $\SplitterDoor = \SplitterOpen$, it returns

Follows from examining a solo execution: the process sets $\SplitterRace$ to
$\Id$, reads $\SplitterOpen$ from $\SplitterDoor$, then reads $\Id$
from $\SplitterRace$.  This causes
it to return as claimed.

To turn this into an $n$-process mutex algorithm, we use the splitter
to separate out at most one process (the one that gets )
onto a fast path that bypasses the slow path taken
by the rest of the processes.  The slow-path process first fight among
themselves to get through an $n$-process mutex; the winner then fights
in a $2$-process mutex with the process (if any) on the fast path.

Releasing the mutex is the reverse of acquiring it.  If I followed the
fast path, I release the $2$-process mutex first then reset the
splitter.  If I followed the slow path, I release the $2$-process
mutex first then the $n$-process mutex.  This gives mutual exclusion
with $O(1)$ cost for any process that arrives before there is any
contention ($O(1)$ for the splitter plus $O(1)$ for the $2$-process

A complication is that if nobody wins the splitter, there is no
fast-path process to reset it.  If we don't want to accept that the
fast path just breaks forever in this case, we have to include a
mechanism for a slow-path process to reset the splitter if it can be
assured that there is no fast-path process left in the system.  The
simplest way to do this is to have each process mark a bit in an array
to show it is present, and have each slow-path process, while still
holding all the mutexes, check on its way out if the $\SplitterDoor$
bit is set and no processes claim to be present.  If it sees all
zeros (except for itself) after seeing $\SplitterDoor =
\SplitterClosed$, it can safely conclude that there is no fast-path
process and reset the splitter itself.  The argument then is that the
last slow-path process to leave will do this, re-enabling the fast
path once there is no contention again.  This approach is taken
implicitly in Lamport's original algorithm, which combines the
splitter and the mutex algorithms into a single miraculous blob.

§.§ Lamport's Bakery algorithm

See <cit.> or <cit.>.

This is a lockout-free mutual exclusion algorithm that uses only
single-writer registers (although some of the registers may end up
holding arbitrarily large values).  Code for the Bakery algorithm is
given as Algorithm <ref>.

$\MTchoosing[i]$, an atomic bit for each $i$, initially 0

$\MTnumber[i]$, an unbounded atomic register, initially 0

Code for process $i$:

$\MTchoosing[i] ← 1$
$\MTnumber[i] ← 1 + \max_{j\ne i} \MTnumber[j]$
$\MTchoosing[i] ← 0$

$j \ne i$
loop until $\MTchoosing[j] = 0$
loop until $\MTnumber[j] = 0$ or
$\langle \MTnumber[i], i \rangle
<\langle \MTnumber[j], j \rangle$

(do critical section stuff)
$\MTnumber[i] ← 0$
(do remainder stuff)

Lamport's Bakery algorithm

Note that several of these lines are actually loops; this is obvious
for Lines <ref>
and <ref>, but is also true for
Line <ref>, which includes an
implicit loop to read all $n-1$ values of $\MTnumber[j]$.

Intuition for mutual exclusion is that if you have a lower number than
I do, then I block waiting for you; for lockout-freedom, eventually I
have the smallest number.
(There are some additional complications involving the bits that we are sweeping under the rug here.)
For a real proof
see <cit.> or <cit.>.

Selling point is a strong near-FIFO guarantee and the use of only single-writer registers (which need not even be atomic—it's enough that they return correct values when no write is in progress).  Weak point is unbounded registers.

§.§ Lower bound on the number of registers

There is a famous result due to Burns and Lynch [83] that
any mutual exclusion protocol using only read/write registers requires
at least $n$ of them.  Details are in <cit.>.
A slightly different version of the
argument is given in <cit.>.
The proof is another nice example of an indistinguishability proof, where we use the fact that if a group of processes can't tell the difference between two executions, they behave the same in both.

Assumptions: We have a protocol that guarantees mutual exclusion and
progress.  Our base objects are all atomic registers.

Key idea: In order for some process $p$ to enter the critical section,
it has to do at least one write to let the other processes know it is
doing so.  If not, they can't tell if $p$ ever showed up at all, so
eventually either some $p'$ will enter the critical section and
violate mutual exclusion or (in the no-$p$ execution) nobody enters
the critical section and we violate progress.  Now suppose we can park
a process $p_{i}$ on each register $r_{i}$ with a pending write to
$i$; in this case we say that $p_{i}$ covercovers
$r_{i}$.  If every register is so covered, we can let $p$ go ahead and
do whatever writes it likes and then deliver all the covering writes
at once, wiping out anything $p$ did.  Now the other processes again
don't know if $p$ exists or not.  So we can say something stronger:
before some process $p$ can enter a critical section, it has to write to an uncovered register.

The hard part is showing that we can cover all the registers without
letting $p$ know that there are other processes waiting—if $p$ can
see that other processes are waiting, it can just sit back and wait
for them to go through the critical section and make progress that
way.  So our goal is to produce states in which (a) processes
$p_{1}\dots{},p_{k}$ (for some $k$) between them cover $k$ registers,
and (b) the resulting configuration is indistinguishable from an
configuration to $p_{k+1}\dots{}p_{n}$, where an idle configuration
is one in which every process is in its remainder section.

Starting from any idle configuration $C$, there exists an execution in
which only processes $p_{1}\dots{}p_{k}$ take steps that leads to a
configuration $C'$ such that (a) $C'$ is indistinguishable by any of
$p_{k+1}\dots{}p_{n}$ from some idle configuration $C''$ and (b)
$k$ distinct registers are covered by $p_{1}\dots{}p_{k}$ in $C'$.

The proof is by induction on $k$.  For $k=0$, let $C'' = C' = C$.

For larger $k$, the essential idea is that starting from $C$, we first
run to a configuration $C_{1}$ where $p_{1}\dots{}p_{k-1}$ cover $k-1$
registers and $C_1$ is indistinguishable from an idle configuration by
the remaining processes, and then run $p_{k}$ until it covers one more
register.  If we let $p_{1}\dots{}p_{k-1}$ go, they overwrite anything
$p_{k}$ wrote.  Unfortunately, they may not come back to covering the
same registers as before if we rerun the induction hypothesis (and in
particular might cover the same register that $p_{k}$ does).  So we
have to look for a particular configuration $C_{1}$ that not only
covers $k-1$ registers but also has an extension that covers the same
$k-1$ registers.

Here's how we find it: Start in $C$.  Run the induction hypothesis to
get $C_{1}$; here there is a set $W_{1}$ of $k-1$ registers covered in
$C_{1}$.  Now let processes $p_{1}$ through $p_{k-1}$ do their pending
writes, then each enter the critical section, leave it, and finish,
and rerun the induction hypothesis to get to a state $C_{2}$,
indistinguishable from an idle configuration by $p_{k}$ and up, in
which $k-1$ registers in $W_{2}$ are covered.  Repeat to get sets
$W_{3}$, $W_{4}$, etc.  Since this sequence is unbounded, and there
are only $\binom{r}{k-1}$ distinct sets of registers to cover (where
$r$ is the number of registers), eventually we have $W_{i} = W_{j}$
for some $i≠j$.  The configurations $C_{i}$ and $C_{j}$ are now
our desired configurations covering the same $k-1$ registers.

Now that we have $C_{i}$ and $C_{j}$, we run until we get to $C_{i}$.
We now run $p_{k}$ until it is about to write some register not
covered by $C_{i}$ (it must do so, or otherwise we can wipe out all of
its writes while it's in the critical section and then go on to
violate mutual exclusion).  Then we let the rest of $p_{1}$ through
$p_{k-1}$ do all their writes (which immediately destroys any evidence
that $p_{k}$ ran at all) and run the execution that gets them to
$C_{j}$.  We now have $k-1$ registers covered by $p_{1}$ through
$p_{k-1}$ and a $k$-th register covered by $p_{k}$, in a configuration that is indistinguishable from idle: this proves the induction step.

The final result follows by the fact that when $k=n$ we cover $n$
registers; this implies that there are $n$ registers to cover.

It's worth noting that the execution constructed in this proof might
be very, very long.  It's not clear what happens if we consider
executions in which, say, the critical section is only entered a
polynomial number of times.  If we are willing to accept a
small probability of failure over polynomially-many entries,
there is a randomized mutex that runs
in $O(\log n)$ space [43].

§ RMR COMPLEXITY

It's not hard to see that we can't build a shared-memory mutex without
busy-waiting: any process that is waiting can't detect that the
critical section is safe to enter without reading a register, but if
that register tells it that it should keep waiting, it is back where
it started and has to read it again.  This makes our standard
step-counting complexity measures useless for describe the worst-case
complexity of a mutual exclusion algorithm.

However, the same argument that suggests we can ignore local
computation in a message-passing model suggests that we can ignore
local operations on registers in a shared-memory model.  Real
multiprocessors have memory hierarchies where memory that is close to
the CPU (or one of the CPUs) is generally much faster than memory that
is more distant.  This suggests charging only for
remote memory referenceremote memory references,
or RMRs, where each register is local to one of the processes and only
operations on non-local registers are expensive.  This has the advantage of more
accurately modeling real costs [189, 53],
and allowing us to build busy-waiting mutual exclusion algorithms with
costs we can actually analyze.

As usual, there is a bit of a divergence here between theory and
practice.  Practically, we are interested in algorithms with good
real-time performance, and RMR complexity becomes a heuristic for
choosing how to assign memory locations.  This gives rise to very
efficient mutual exclusion algorithms for real machines, of which the
most widely used is the beautiful MCS algorithm of Mellor-Crummey and
Scott [189].  Theoretically, we are interested in
the question of how efficiently we can solve mutual exclusion in
our formal model, and RMR complexity becomes just another complexity
measure, one that happens to allow busy-waiting on local variables.

§.§ Cache-coherence vs. distributed shared memory

The basic idea of RMR complexity is that a process doesn't pay for
operations on local registers.  But what determines which operations
are local?

In the cache-coherent model (CC for short), once a process
reads a register it retains a local copy as long as nobody updates it.
So if I do a sequence
of read operations with no intervening operations by other processes,
I may pay an RMR for the first one (if my cache is out of date), but the rest are free.
The assumption is that each process can cache registers, and there is some
cache-coherence protocol that guarantees that all the caches stay up
to date.  We may or may not pay RMRs for write operations or other
read operations, depending on the details of the cache-coherence
protocol, but for upper bounds it is safest to assume that we do.

In the
distributed shared memory model (DSM), each register is
assigned permanently to a single process.  Other processes can read or
write the register, but only the owner gets to do so without paying an
RMR.  Here memory locations are nailed down to specific processes.

In general, we expect the cache-coherent model to be cheaper than the
distributed shared-memory model, if we ignore constant factors.  The
reason is that if we run a DSM algorithm in a CC model, then the
process $p$ to which a register $r$ is assigned incurs an RMR only if
some other process $q$ accesses $p$ since $p$'s last access.
But then we can amortize $p$'s RMR by charging $q$ double.  Since $q$
incurs an RMR in the CC model, this tells us that we pay at most twice
as many RMRs in DSM as in CC for any algorithm.

The converse is not true: there are (mildly exotic) problems for which
it is known that CC algorithms are asymptotically more efficient than
DSM algorithms [145, 105].

§.§ RMR complexity of Peterson's algorithm

As a warm-up,
let's look at the RMR complexity of
Peterson's two-process mutual exclusion algorithm
(Algorithm <ref>).
Acquiring the mutex requires going through mostly straight-line code,
except for the loop that tests $\MTpresent[¬ i]$ and $\MTwaiting$.

In the DSM model, spinning on $\MTpresent[¬ i]$ is not a problem
(we can make it a local variable of process $i$).  But $\MTwaiting$ is
trouble.  Whichever process we don't assign it to will pay an RMR
every time it looks at it.  So Peterson's algorithm behaves badly by
the RMR measure in this model.

Things are better in the CC model.  Now process $i$ may pay RMRs for
its first reads of $\MTpresent[¬ i]$ and $\MTwaiting$, but any
subsequent reads are free unless process $¬ i$ changes one of them.
But any change to either of the variables causes process $i$ to leave
the loop.  It follows that process $i$ pays at most 3 RMRs to get
through the busy-waiting loop, giving an RMR complexity of $O(1)$.

RMR complexities for parts of a protocol that access different
registers add just like step complexities, so the Peterson-Fischer
tree construction described in §<ref>
works here too.  The result is $O(\log n)$ RMRs per critical section
access, but only in the CC model.

§.§ Mutual exclusion in the DSM model

Yang and Anderson [226] give a mutual exclusion algorithm
for the DSM model that requires $Θ(\log n)$ RMRs to reach the
critical section.
This is now known to be optimal for deterministic
algorithms [44].  The core of the algorithm is a
$2$-process mutex similar to Peterson's, with some tweaks so that each
process spins only on its own registers.  Pseudocode is given in
Algorithm <ref>; this is adapted from

$C[\YAside(i)] ← i$
$T ← i$
$P[i] ← 0$
$\YArival ← C[¬ \YAside(i)]$
$\YArival \ne ⊥$ $T = i$
$P[\YArival] = 0$
$P[\YArival] = 1$

$P[i] = 0$spin
$T = i$
$P[i] ≤ 1$spin

critical section goes here
$C[\YAside(i)] ← ⊥$
$\YArival ← T$
$\YArival \ne i$
$P[\YArival] ← 2$

Yang-Anderson mutex for two processes

The algorithm is designed to be used in a tree construction where a
process with id in the range $\{1\dots n/2\}$ first fights with all
other processes in this range, and similarly for processes in the
range $\{n/2+1 \dots n\}$.  The function $\YAside(i)$ is $0$ for the
first group of processes and $1$ for the second.  The variables $C[0]$
and $C[1]$ are used to record which process is the winner for each
side, and also take the place of the $\MTpresent$ variables in
Peterson's algorithm.  Each process has its own variable $P[i]$ that it spins on when
blocked; this variable is initially $0$ and ranges over $\{0,1,2\}$;
this is used to signal a process that it is safe to proceed, and
tests on $P$ substitute for tests on the non-local variables in Peterson's algorithm.
Finally, the variable $T$ is used (like $\MTwaiting$ in
Peterson's algorithm) to break ties: when $T = i$, it's $i$'s turn to

Initially, $C[0] = C[1] = ⊥$ and $P[i] = 0$ for all $i$.

When I want to enter my critical section, I first set
$C[\YAside(i)]$ so you can find me; this also has the same effect as
setting $\MTpresent[\YAside(i)]$ in Peterson's algorithm.
I then point $T$ to
myself and look for you.
I'll block if I see $C[¬ \YAside(i)] = 1$ and $T=i$.  This can
occur in two ways: one is that I really write $T$ after you did, but
the other is that you only wrote $C[¬ \YAside(i)]$ but haven't
written $T$ yet.  In the latter case, you will signal to me that $T$
may have changed by setting $P[i]$ to $1$.  I have to check $T$ again
(because maybe I really did write $T$ later), and if it is still $i$,
then I know that you are ahead of me and will succeed in entering your
critical section.  In this case I can safely spin on $P[i]$ waiting
for it to become $2$, which signals that you have left.

There is a proof that this actually works in [226], but it's 27
pages of very meticulously-demonstrated invariants (in fairness, this
includes the entire algorithm, including the tree parts that we
omitted here).  For intuition, this is not much more helpful than
having a program mechanically check all the transitions, since the
algorithm for two processes is effectively finite-state if we ignore
the issue with different processes $i$ jumping into the role of

A slightly less rigorous but more human-accessible proof
would be analogous to the proof of Peterson's algorithm.
We need to show two things: first, that no two processes ever both
enter the critical section, and second, that no process gets stuck.

For the first part, consider two processes $i$ and $j$, where
$\YAside(i) = 0$ and $\YAside(j) = 1$.  We can't have both $i$ and $j$
skip the loops, because whichever one writes $T$ last sees itself in
$T$.  Suppose that this is process $i$ and that $j$ skips the loops.
Then $T=i$ and $P[i] = 0$ as long as $j$ is in the critical section,
so $i$ blocks.  Alternatively, suppose $i$ writes $T$ last but does so
after $j$ first reads $T$.  Now $i$ and $j$ both enter the loops.  But
again $i$ sees $T=i$ on its second test and blocks on the second loop
until $j$ sets $P[i]$ to $2$, which doesn't happen until after $j$
finishes its critical section.

Now let us show that $i$ doesn't get stuck.  Again we'll assume that
$i$ wrote $T$ second.

If $j$ skips the loops, then
$j$ sets $P[i] = 2$ on its way out as long as $T=i$; this falsifies both loop tests.
If this happens after $i$ first sets $P[i]$ to 0,
only $i$ can set $P[i]$ back to $0$, so $i$ escapes its first loop,
any $j'$ that enters from the $1$ side will see $P[i]=2$ before
attempting to set $P[i]$ to $1$, so $P[i]$ remains at $2$ until $i$
comes back around again.  If $j$ sets $P[i]$ to 2 before $i$ sets $P[i]$ to
$0$ (or doesn't set it at all because $T=j$,
then $C[\YAside(j)]$ is set to $⊥$ before $i$ reads it, so $i$
skips the loops.

If $j$ doesn't skip the loops, then $P[i]$ and $P[j]$ are both set to
$1$ after $i$ and $j$ enter the loopy part.  Because $j$ waits for
$P[j] \ne 0$, when it looks at $T$ the second time it will see $T=i
\ne j$ and will skip the second loop.  This causes it to eventually
set $P[i]$ to 2 or set $C[\YAside(j)]$ to $⊥$ before $i$ reads it
as in the previous case, so again $i$ eventually
reaches its critical section.

Since the only operations inside a loop are on local variables, the
algorithm has $O(1)$ RMR complexity.  For the full tree this becomes
$O(\log n)$.

§.§ Lower bounds

For deterministic algorithms, there is a lower bound due to Attiya,
Hendler, and Woelfel [44] that shows that any one-shot
mutual exclusion algorithm for $n$ processes incurs $\Omega(n \log n)$
total RMRs in either the CC or DSM models (which implies that some
single process incurs $\Omega(\log n)$ RMRs).  This is based on an earlier
breakthrough lower bound of Fan and Lynch [126] that proved
the same lower bound for the number of times a register changes state.
Both bounds are information-theoretic:
a family of $n!$
executions is constructed containing all possible orders in which the processes enter
the critical section, and it is shown that each RMR or state change only
contributes $O(1)$ bits to choosing between them.

For randomized algorithms, Hendler and Woelfel [163]
have an algorithm that uses $O(\log n/\log \log n)$ expected RMRs
against an adaptive adversary, beating the deterministic lower bound.
This is the best possible for an adaptive adversary, due to a matching lower bound of
Giakkoupis and Woelfel [149] that holds even for
systems that provide compare-and-swap objects.

For an oblivious adversary,
an algorithm of Giakkoupis and Woelfel [150] achieves
$O(1$) expected RMRs in the DSM model.
With compare-and-swap, a more recent algorithm of Giakkoupis and
Woelfel [151] gives $O(1)$ expected RMRs in the CC
model.  Curiously, there also exist linearizable $O(1)$-RMR implementations of CAS
from registers in this model [138]; however, it is not clear that these
implementations can be combined with the Giakkoupis-Woelfel algorithm
to give $O(1)$ expected RMRs using registers, because variations in
scheduling of randomized implementations may produce subtle
conditioning that gives different behavior from actual atomic objects
in the context of a randomized algorithm [141].

The wait-free hierarchy2020

In a shared memory model, it may be possible to solve some problems
using wait-free protocols, in which any process can finish
the protocol in a bounded number of steps, no matter what the other
processes are doing (see Chapter <ref> for more on this and some variants).

The hierarchy!wait-freewait-free hierarchy
$h^{r}_{m}$ classifies asynchronous shared-memory object types $T$ by
consensus number, where a type $T$ has consensus number $n$
if with objects of type $T$ and atomic registers (all initialized to
appropriate values[The justification for assuming that the
objects can be initialized to an arbitrary state is a little tricky.
The idea is that if we are trying to implement consensus from objects
of type $T$ that are themselves implemented in terms of objects of
type $S$, then it's natural to assume that we initialize our simulated
type-$T$ objects to whatever states are convenient.  Conversely, if we
are using the ability of type-$T$ objects to solve $n$-process
consensus to show that they can't be implemented from type-$S$ objects
(which can't solve $n$-process consensus), then for both the type-$T$
and type-$S$ objects we want these claims to hold no matter how they
are initialized.]) it is possible to solve wait-free consensus (i.e.,
agreement, validity, wait-free termination) for $n$ processes but not
for $n+1$ processes.  The consensus number of any type is at least
$1$, since $1$-process consensus requires no interaction, and may
range up to $\infty$ for particularly powerful objects.

The general idea is that a type $T$ with consensus number
$c$ can't simulate at type $T'$ with a higher consensus number $c'$,
because then we could use the simulation to convert a $c'$-process
consensus protocol using $T'$ into a $c'$-process consensus protocol
using $T$.  The converse claim, that objects with the same or higher consensus
numbers can simulate those with lower ones, is not necessarily true:
even though $n$-process consensus can implement any object for $n$
processes (see §<ref>), it may be that
for more than $n$ processes there is some object that has consensus
number $n$ but that cannot be implemented from an arbitrary
$n$-consensus object.[The existence of such objects was
eventually demonstrated by Afek, Ellen, and Gafni [28].]

The wait-free hierarchy was suggested by work by Maurice
Herlihy [153]
that classified many common (and some uncommon) shared-memory objects
by consensus number, and showed that an unbounded collection of
objects with consensus number $n$ together with atomic registers gives
a wait-free implementation of any object in an $n$-process system.

Various subsequent authors noticed that this did not give a
hierarchy!robustrobust hierarchy in the sense that combining two types of objects
with consensus number $n$ could solve wait-free consensus for larger
and the hierarchy $h^{r}_{m}$ was proposed by Prasad
Jayanti [166]
as a way of
classifying objects that might be robust: an object is at level $n$ of
the $h^{r}_{m}$ hierarchy if having unboundedly many objects plus
unboundedly many registers solves $n$-process wait-free consensus but
not $(n+1)$-process wait-free consensus.[The $r$ in $h^r_m$
stands for the registers, the $m$ for having many objects of the given
type.  Jayanti [166] also defines a hierarchy $h^r_1$
where you only get finitely many objects.
The $h$ stands for “hierarchy,” or, more specifically, $h(T)$ stands
for the level of the hierarchy at which $T$ appears [169].]

Whether or not the resulting
hierarchy is in fact robust for arbitrary deterministic objects is
still open, but Ruppert [215]
subsequently showed that it is robust for RMW registers and objects
with a read operation that returns the current state, and there is a
paper by Borowsky, Gafni, and Afek [79]
sketches a proof based on a topological characterization of
computability[See Chapter <ref>.] that $h^{r}_{m}$ is robust for deterministic objects that
don't discriminate between processes (unlike, say, single-writer
registers).  So for well-behaved shared-memory objects (deterministic, symmetrically accessible, with read operations, etc.),
consensus number appears to give a real classification that allows us
to say for example that any collection of read-write registers
(consensus number $1$), fetch-and-increments ($2$), test-and-set bits
($2$), and queues ($2$) is not enough to build a compare-and-swap
($\infty$).[Ruppert's paper is particularly handy because it gives an
algorithm for computing the consensus number of the objects it
considers.  However, for infinite-state objects, this requires solving
the halting problem (as previously shown by Jayanti and
Toueg [170].]

Another useful result from the Borowsky-Gafni-Afek paper is that the
consensus number is not generally dependent on what assumptions we
make about the initial state of the objects. Specifically, <cit.> states that as long as there is some sequence of
operations that takes an object from a fixed initial state to a
desirable initial state for consensus, then we can safely assume that
the object is in the desirable state. The core idea of the proof is
that each process can initialize its own copy of the object and then
announce that it is ready; each process will then participate in a
sequence of consensus protocols using the objects that they observe are
ready, with the output of each protocol used as the input to the next.
Because the first object $S_i$ to be announced as initialized will be
visible to all processes, they will all do consensus using $S_i$. Any
subsequent protocols that may be used by only a subset of the
processes will not change the common agreed output from the $S_i$
protocol.[The result in the paper is stated for a consensus
protocol that uses a single copy of the
object, but it generalizes in the obvious way to those that use multiple copies of
the object.]

When considering multiple objects, the usual assumption is that
objects are combined by putting them next to each other.  If we
can combine two objects by constructing a single object with
operations of both—which is essentially what happens when we apply
different machine language instructions to the same memory
location—then the object with both operations may have a higher consensus number
than the object with either operation individually.
This was observed by Ellen  [114].  A simple
example would be a register than supports increment ($+1$) and
doubling ($×2$) operations.  A register with only one of these
operations is equivalent to a counter and has consensus number $1$.
But a register with both operations has consensus number at least $2$,
since if it is initialized to $2$, we can tell which of the two
operations went first by looking at the final value: $3 = 2+1, 4 =
2×2, 5=(2×2)+1, 6 = (2+1)×2$.

We won't attempt to do the robustness proofs of
Borowsky  [79] or Ruppert [215].
Instead, we'll concentrate on Herlihy's original results and show that
specific objects have specific consensus numbers when used in
isolation.  The procedure in each case will be to show an upper bound
on the consensus number using a variant of Fischer-Lynch-Paterson
(made easier because we are wait-free and don't have to worry about
fairness) and then show a matching lower bound (for non-trivial upper
bounds) by exhibiting an $n$-process consensus protocol for some $n$.
Essentially everything below is taken from Herlihy's
paper [153], so reading that may make more sense
than reading these notes.

§ CLASSIFICATION BY CONSENSUS NUMBER

Here we show the position of various types in the wait-free hierarchy.
The quick description is shown in
Table <ref>; more details (mostly adapted
from [153]) are given below.

Consensus number   Defining    Examples

1   Read with  no-return RMW.
, , atomic snapshots.

2   Interfering RMW; queue-like structures.   Test-and-set,
, queues, .

$m$       $m$-process consensus objects.

$2m-2$       Atomic $m$-register write.

$\infty$   First write-like operation wins.   Queue with peek,
fetch-and-cons, sticky bits, compare-and-swap, memory-to-memory swap,
memory-to-memory copy.

Position of various types in the wait-free hierarchy

§.§ Level 1: atomic registers, counters, other interfering RMW registers that don't return the old value

First observe that any type has consensus number at least 1, since 1-process consensus is trivial.

We'll argue that a large class of particularly weak objects has
consensus number exactly 1, by running FLP with 2 processes.  Recall
from Chapter <ref> that in the
Fischer-Lynch-Paterson [130]
proof we classify states as bivalent or univalent depending on whether
both decision values are still possible, and that with at least one
failure we can always start in a bivalent state (this doesn't depend
on what objects we are using, since it depends only on having
invisible inputs).  Since the system is wait-free there is no
constraint on adversary scheduling, and so if any bivalent state has a
bivalent successor we can just do it.  So to solve consensus we have
to reach a bivalent configuration $C$ that has only univalent
successors, and in particular has a 0-valent and a 1-valent successor
produced by applying operations $x$ and $y$ of processes $p_{x}$ and

Assuming objects don't interact with each other behind the scenes, $x$
and $y$ must be operations of the same object.  Otherwise $Cxy = Cyx$ and we get a contradiction.

Now let's suppose we are looking at atomic registers, and consider cases:

* $x$ and $y$ are both reads,   Then $x$ and $y$ commute: $Cxy =
Cyx$, and we get a contradiction.

* $x$ is a read and $y$ is a write.  Then $p_{y}$ can't tell the
difference between $Cyx$ and $Cxy$, so running $p_{y}$ to completion
gives the same decision value from both $Cyx$ and $Cxy$, another contradiction.

* $x$ and $y$ are both writes.  Now $p_{y}$ can't tell the
difference between $Cxy$ and $Cy$, so we get the same decision value
for both, again contradicting that $Cx$ is 0-valent and $Cy$ is 1-valent.

There's a pattern to these cases that generalizes to other objects.
Suppose that an object has a read operation that returns its state and
one or more read-modify-write operations that don't return anything
(perhaps we could call them “modify-write” operations).  We'll say
that the MW operations are
interfering operationsinterfering
if, for any two operations $x$ and $y$, either:

* $x$ and $y$
commuting operationscommute: $Cxy = Cyx$.

* One of $x$ and $y$
overwriting operationsoverwrites the other: $Cxy =
Cy$ or $Cyx = Cx$.

Then no pair of read or modify-write operations can get us out of a
bivalent state, because (a) reads commute; (b) for a read and MW, the
non-reader can't tell which operation happened first; (c) and for any
two MW operations, either they commute or the overwriter can't detect
that the first operation happened.  So any MW object with
uninformative, interfering MW operations has consensus number 1.

example, consider a counter that supports operations read, increment,
decrement, and write: a write overwrites any other operation, and
increments and decrements commute with each other, so the counter has
consensus number 1.  The same applies to a generalized counter that
supports an atomic $x ← x+a$ operation; as long as this operation
doesn't return the old value, it still commutes with other atomic

Max registers [5], which have read operations that return the largest value
previously written, also have commutative updates, so they also have
consensus number 1.  This gives an example of an object not invented
at the time of Herlihy's paper that is still covered by Herlihy's

§.§ Level 2: interfering RMW objects that return the old value, queues (without peek)

Suppose now that we have a RMW object that returns the old value, and
suppose that it is non-trivial in the sense that it has at
least one RMW operation where the embedded function $f$ that
determines the new value is not the identity (otherwise RMW is just
read).  Then there is some value $v$ such that $f(v) \ne v$.  To solve
two-process consensus, have each process $p_{i}$ first write its
preferred value to a register $r_{i}$, then execute the non-trivial
RMW operation on the RMW object initialized to $v$.  The first process
to execute its operation sees $v$ and decides its own value.  The
second process sees $f(v)$ and decides the first process's value (which it reads from the register).  It follows that non-trivial RMW object has consensus number at least 2.

In many cases, this is all we get.  Suppose that the operations of
some RMW type $T$ are non-interfering in a way analogous to the previous
definition, where now we say that $x$ and $y$ commute if they leave
the object in the same state (regardless of what values are returned)
and that $y$ overwrites $x$ if the object is always in the same state
after both $x$ and $xy$ (again regardless of what is returned).  The
two processes $p_x$ and $p_y$ that carry out $x$ and $y$ know what happened, but a
third process $p_z$ doesn't.  So if we run $p_z$ to completion we get the
same decision value after both $Cx$ and $Cy$, which means that $Cx$
and $Cy$ can't be 0-valent and 1-valent.  It follows that no collection of RMW registers with interfering operations can solve 3-process consensus, and thus all such objects have consensus number 2.
Examples of these objects include test-and-set bits,
fetch-and-add registers, and swap registers that
support an operation that writes a new value and
returns the previous value.

There are some other objects with consensus number 2 that don't fit this pattern.  Define a
queue!wait-freewait-free queue as an object with
enqueue and dequeue operations (like normal queues), where dequeue
returns $⊥$ if the queue is empty (instead of blocking).  To solve
2-process consensus with a wait-free queue, initialize the queue with
a single value (it doesn't matter what the value is).  We can then
treat the queue as a non-trivial RMW register where a process wins if
it successfully dequeues the initial value and loses if it gets
empty.[But wait!  What if the queue starts empty?

This turns out to be a surprisingly annoying problem, and was one of
the motivating examples for $h^r_m$ as opposed to Herlihy's vaguer
initial definition.

With one empty queue and nothing else, Jayanti and
Toueg <cit.> show that there is no solution to
consensus for two processes.  This is also true for stacks (Theorem 8
from the same paper).  But adding a register (Theorem 9) lets you do
it.  A second empty queue also works.]

However, enqueue operations are non-interfering: if $p_{x}$ enqueues
$v_{x}$ and $p_{y}$ enqueues $v_{y}$, then any third process can
detect which happened first; similarly we can distinguish
$\Enq(x) \Deq()$ from $\Deq() \Enq(x)$.  So to show we can't do three
process consensus we do something sneakier: given a bivalent state $C$
with allegedly 0- and 1-valent successors $C \Enq(x)$ and $C \Enq(y)$,
consider both $C \Enq(x) \Enq(y)$ and $C \Enq(y) \Enq(x)$ and run $p_x$ until it
does a $\Deq()$ (which it must, because otherwise it can't tell what to
decide) and then stop it.  Now run $p_y$ until it also does a $\Deq()$ and
then stop it.  We've now destroyed the evidence of the split and poor
hapless $p_z$ is stuck.
In the case of $C \Deq() \Enq(x)$ and $C \Enq(x) \Deq()$
on a non-empty queue we can kill the initial dequeuer immediately and
then kill whoever dequeues $x$ or the value it replaced, and if the
queue is empty only the dequeuer knows.  In either case we reach
indistinguishable states after killing only 2 witnesses, and the queue
has consensus number at most 2.

Similar arguments work on stacks, deques, and so forth—these all have consensus number exactly 2.

§.§ Level infinity: objects where the first write wins

These are objects that can solve consensus for any number of
Here are a bunch of level-$\infty$ objects:

Queue with peek queue!with peek Has operations
$\Enq(x)$ and $\Peek()$, which
returns the first value enqueued.  (Maybe also $\Deq()$, but we don't
need it for consensus).  Protocol is to enqueue my input and then
peek and return the first value in the queue.

Fetch-and-cons fetch-and-cons Returns old cdr and adds new
car on to the head of a list.  Use preceding protocol where
$\Peek() = \FuncSty{tail}(\DataSty{car}::\DataSty{cdr})$.

Sticky bit sticky bit Has a $\Write$ operation that
has no effect unless register
is in the initial $⊥$ state.  Whether the $\Write$ succeeds or
fails, it returns nothing.
The consensus protocol is to write my input and then return result of a read.

Compare-and-swap compare-and-swapCAS Has $\FuncSty{CAS}(\DataSty{old},
\DataSty{new})$ operation that writes new only if previous
value is old.  Use it to build a sticky bit.

load-linked/stored-conditionalLL/SC Like
compare-and-swap split into
two operations.  The load-linked operation reads a
memory location and marks it.  The store-conditional
operation succeeds only if the location has not been changed since
the preceding load-linked by the same process.  Can be used to build
a sticky bit.

Memory-to-memory swap
swap!memory-to-memorymemory-to-memory swap
Has $\Swap(r_{i}, r_{j})$
operation that atomically swaps contents of $r_{i}$ with $r_{j}$, as
well as the usual read and write operations for all registers.  Use
to implement fetch-and-cons.  Alternatively, use two registers
$\Input[i]$ and $\SwapVictory[i]$ for each process $i$, where
$\SwapVictory[i]$ is initialized to 0, and a single central register
, initialized to 1.  To execute consensus, write your
input to $\Input[i]$, then swap $\SwapVictory[i]$ with
.  The winning value is obtained by scanning all the
registers for the one that contains a 1, then returning
the corresponding $\Input$ value.)

Memory-to-memory copy
memory-to-memory copy
Has a $\FuncSty{copy}(r_{i}, r_{j})$
operation that copies $r_{i}$ to $r_{j}$ atomically.
Use the same trick as for memory-to-memory swap, where a process
copies to $\SwapVictory[i]$.  But now we have a process
follow up by writing $0$ to .  As soon as this happens, the
$\SwapVictory$ values are now fixed; take the leftmost $1$ as the
winner.[Or use any other rule that all processes apply

Herlihy [153] gives a slightly more complicated version
of this procedure, where there is a separate $\SwapPrize[i]$
register for each $i$, and after doing its copy a process writes $0$
to all of the registers.  This shows that memory-to-memory
copy solves consensus for arbitrarily many processes even if we
insist that copy operations can never overlap.
The same trick also works for memory-to-memory swap, since we can
treat a memory-to-memory swap as a memory-to-memory copy given that we don't
care what value it puts in the $\SwapPrize[i]$ register.

Bank accounts A bank account object stores a
non-negative integer, and supports a operation that returns
the current value and a $\FuncSty{withdraw}(k)$ operation that
reduces the value by $k$, unless this would reduce the value
below $0$, in which case it has no effect.

To solve (binary) consensus with a bank account, start it with $3$, and
have each process with input $b$ attempt to withdraw $3-b$ from
the account.  After the first withdrawal, the object will hold
either $0$ or $1$, and no further withdrawals will have any
effect.  So the bank account acts exactly like a sticky bit where
$3$ represents $⊥$.[If you have more money,
you can extend this construction to any fixed set of
values.  For example, to choose among values $v$ in $0\dots m-1$, start with
$2m$ and have a process with input $v$ subtract $2m-v$.]

For many years, I assumed that this example demonstrated why
cryptocurrencies all seem to use embedded consensus protocols of
some sort. However, it turns out that there is a critical
assumption needed for this proof, which is that more than one
process can spend from the same account.
Without this assumption, it has been shown by
Guerraoui  [143] that the consensus number of
a single-spender bank account is $1$, and more generally that the
consensus number of a $k$-spender bank account is exactly $k$.

§.§ Level 2m-2: simultaneous
m-register write

Here we have a (large) collection of atomic registers augmented by an
$m$-register write operation that performs all the writes
simultaneously.  The intuition for why this is helpful is that if
$p_{1}$ writes $r_{1}$ and $r_{\MultiWriteShared}$ while $p_{2}$ writes
$r_{2}$ and $r_{\MultiWriteShared}$ then any process can look at the
state of $r_{1}$, $r_{2}$ and $r_{\MultiWriteShared}$ and tell which
write happened first.  Code for this procedure is given in
Algorithm <ref>; note that up to 4 reads may be
necessary to determine the winner because of timing
issues.[The main issue is that processes can only read the
registers one at a time.  An alternative to running
Algorithm <ref> is to use a double-collect
snapshot (see §<ref>) to simulate reading
all three registers at once.  However, this might require as many
as twelve read operations, since a process doing a snapshot has to re-read
all three registers if any of them change.]

$v_1 ← r_1$
$v_2 ← r_2$
$v_1 = v_2 = ⊥$
no winner

$v_1 = 1$ $v_2 = ⊥$
$p_1$ went first

read $r_1$ again
$v_1' ← r_1$
$v_2 = 2$ $v_1' = ⊥$
$p_2$ went first

both $p_1$ and $p_2$ wrote
$r_{\MultiWriteShared} = 1$

[Determining the winner of a race between 2-register
writes]Determining the winner of a race between 2-register writes.
The assumption is that $p_1$ and $p_2$ each wrote their own ids to
$r_i$ and $r_\MultiWriteShared$ simultaneously.  This code can be
executed by any process (including but not limited to $p_1$ or $p_2$)
to determine which of these 2-register writes happened first.

The workings of Algorithm <ref> are straightforward:

* If the process reads $r_{1} = r_{2} = ⊥$, then we don't care which went first, because the reader (or somebody else) already won.

* If the process reads $r_{1} = 1$ and then $r_{2} = ⊥$, then
$p_{1}$ went first.

* If the process reads $r_{2} = 2$ and then $r_{1} = ⊥$, then
$p_{2}$ went first.  (This requires at least one more read after checking the first case.)

* Otherwise the process saw $r_{1} = 1$ and $r_{2} = 2$.  Now
read $r_{\MultiWriteShared}$: if it's 1, $p_{2}$ went first; if it's
$2$, $p_1$ went first.

Algorithm <ref>
requires 2-register writes, and will give us a protocol for 2
processes (since the reader above has to participate somewhere to make
the first case work).  For $m$ processes, we can do the same thing
with $m$-register writes.  We have a register $r_{pq} = r_{qp}$ for
each pair of distinct processes $p$ and $q$, plus a register $r_{pp}$
for each $p$; this gives a total of $\binom{m}{2} + m = O(m^{2})$
registers.  All registers are initialized to $⊥$.  Process $p$ then
writes its initial preference to some single-writer register
$\DataSty{pref}_{p}$ and then simultaneously writes $p$ to $r_{pq}$
for all $q$ (including $r_{pp}$).  It then attempts to figure out the
first writer by applying the above test for each $q$ to $r_{pq}$
(standing in for $r_{\MultiWriteShared}$), $r_{pp}$ ($r_{1}$) and
$r_{qq}$ ($r_{2}$).  If it won against all the other processes, it
decides its own value.  If not, it repeats the test recursively for
some $p'$ that beat it until it finds a process that beat everybody,
and returns its value.  So $m$-register writes solve $m$-process wait-free consensus.

A further tweak gets $2m-2$: run two copies of an $(m-1)$-process
protocol using separate arrays of registers to decide a winner for
each group.  Then add a second phase where processes contend across
the groups.  This
involves each process $p$ from group $1$ writing the
winning id for its group simultaneously into $s_{p}$ and $s_{pq}$ for
each $q$ in the other group.  To figure out who won in the end, build
a graph of all victories, where there is an edge from $p$ to $q$ if
and only if $p$ beat $q$ in Phase 1 or $p$'s id was written before $q$'s id in Phase 2.  The winner is the (unique) process with at least one outgoing edge and no incoming edges, which will be the process that won its own group (by writing first) and whose value was written first in Phase 2.

One thing to note about the second phase is that, unlike mutex, we
can't just have the winners of the two groups fight each other, since
this would not give the wait-free property for non-winners.  Instead,
we have to allow a non-winner $p$ to pick up the slack for a slow winner
and fight on behalf of the entire group.  This requires an $m$-process
write operation to write $s_p$ and all $s_{pq}$ at once.

§.§.§ Matching impossibility result

It might seem that the technique used to boost from $m$-process
consensus to $(2m-2)$-process consensus could be repeated to get up to
at least $Θ(m^{2})$, but this turns out not to be the case.  The
essential idea is to show that in order to escape bivalence, we have
to get to a configuration $C$ where every process is about to
do an $m$-register write leading to a univalent configuration (since
reads don't help for the usual reasons, and normal writes can be
simulated by $m$-register writes with an extra $m-1$ dummy registers),
and then argue that these writes can't overlap too much.  So suppose
we are in such a configuration, and suppose that $Cx$ is 0-valent and
$Cy$ is 1-valent, and we also have many other operations
$z_{1}\dots{}z_{k}$ that lead to univalent states.  Following
Herlihy [153], we argue in two steps:

* There is some register that is written to by $x$ alone out of
all the pending operations.  Proof: Suppose not.  Then the 0-valent
configuration $Cxyz_{1}\dots{}z_{k}$ is indistinguishable from the
1-valent configuration $Cyz_{1}\dots{}z_{k}$ by any process except
$p_{x}$, and we're in trouble.

* There is some register that is written to by $x$ and $y$ but
not by any of the $z_{i}$.  Proof:: Suppose not.
The each register is written by at most one of $x$ and $y$, making it
useless for telling which went first; or it is overwritten by some
$z_i$, hiding the value that tells which went first.  So
$Cxyz_{1}\dots{}z_{k}$ is indistinguishable from
$Cyxz_{1}\dots{}z_{k}$ for any process other than $p_{x}$ and
$p_{y}$, and we're still in trouble.

Now suppose we have $2m-1$ processes.  The first part says that each
of the pending operations ($x$, $y$, all of the $z_{i}$) writes to 1
single-writer register and at least $k$ two-writer registers where $k$
is the number of processes leading to a different univalent value.
This gives $k+1$ total registers simultaneously written by this
operation.  Now observe that with $2m-1$ process, there is some set of
$m$ processes whose operations all lead to a $b$-valent state; so for
any process to get to a ($¬{}b$)-valent state, it must write $m+1$
registers simultaneously. It follows that with only $m$ simultaneous
writes we can only do $(2m-2)$-consensus.

§.§ Level m: m-process consensus objects

An $m$-process consensus object has a single
consensus operation that, the first $m$ times it is called,
returns the input value in the first operation, and thereafter returns
only $⊥$.  Clearly this solves $m$-process consensus.  To show that
it doesn't solve $(m+1)$-process consensus even when augmented with
registers, run a bivalent initial configuration to a configuration $C$
where any further operation yields a univalent state.  By an argument
similar to the $m$-register write case, we can show that the pending
operations in $C$ must all be consensus operations on the same
consensus object (anything else commutes or overwrites).  Now run
$Cxyz_{1}\dots{}z_{k}$ and $Cyxz_{1}\dots{}z_{k}$, where $x$ and $y$
lead to 0-valent and 1-valent states, and observe that $p_{k}$ can't
distinguish the resulting configurations because all it got was
$⊥$.  (Note: this works even if the consensus object isn't in its
initial state, since we know that before $x$ or $y$ the configuration is still bivalent.)

So the $m$-process consensus object has consensus number $m$.  This
shows that $h^{r}_{m}$ is nonempty at each level.

A natural question at this point is whether the inability of
$m$-process consensus objects to solve $(m+1)$-process consensus
implies robustness of the hierarchy.  One might consider the following
argument: given any object at level $m$, we can simulate it with an
$m$-process consensus object, and since we can't combine $m$-process
consensus objects to boost the consensus number, we can't combine any
objects they can simulate either.  The problem here is that while
$m$-process consensus objects can simulate any object in a system with
$m$ processes (see below), it may be that some objects can do more in
a system with $m+1$ objects while still not solving $(m+1)$-process
consensus.  A simple way to see this would be to imagine a variant of
the $m$-process consensus object that doesn't fail completely after
$m$ operations; for example, it might return one of the first two
inputs given to it instead of $⊥$.  This doesn't help with solving
consensus, but it might (or might not) make it too powerful to
implement using standard $m$-process consensus objects.

§ UNIVERSALITY OF CONSENSUS

consensus!universality of
universality of consensusUniversality of consensus says that any type that can implement $n$-process consensus can,
together with atomic registers, give a wait-free implementation of any
object in a system with $n$ processes.  That consensus is universal
was shown by Herlihy [153] and
Plotkin [204].  Both of these papers spend a lot of
effort on making sure that both the cost of each operation and the
amount of space used is bounded.  But if we ignore these constraints,
the same result can be shown using a mechanism similar to the
replicated state machines of

Here the processes repeatedly use consensus to decide between
candidate histories of the simulated object, and a process
successfully completes an operation when its operation (tagged to
distinguish it from other similar operations) appears in a winning
history.  A round structure avoids too much confusion.

Details are given in Algorithm <ref>.

announce my intended operation
$\UniversalOp[i] ← π$

find a recent round
$r ← \max_j \UniversalRound[j]$
obtain the history as of that round
$h_r = ⊥$
$h_r ← \UniversalConsensus(c[r], ⊥)$

$π \in h_r$
value $π$ returns in $h_r$

else attempt to advance
$h' ← h_r$
$\UniversalOp[j] \not\in h'$
append $\UniversalOp[j]$ to $h'$

$h_{r+1} ← \UniversalConsensus(c[r+1], h')$
$\UniversalRound[i] ← r+1$

A universal construction based on consensus

There are some subtleties to this algorithm.  The first time that a
process calls consensus (on $c[r]$), it may supply a dummy input; the
idea is that it is only using the consensus object to obtain the
agreed-upon history from a round it missed.  It's safe to do this,
because no process writes $r$ to its register until
$c[r]$ is complete, so the dummy input can't be accidentally chosen as
the correct value.

It's not hard to see that whatever $h_{r+1}$ is chosen in $c[r+1]$ is an
extension of $h_r$ (it is constructed by appending operations to
$h_r$), and that all processes agree on it (by the agreement property
of the consensus object $c[r+1]$.  So this gives us an increasing
sequence of consistent histories.
We also need
to show that these histories are linearizable.
The obvious linearization is just the most
recent version of $h_r$.  Suppose some call to
$\UniversalApply(π_1)$ finishes before a call to
$\UniversalApply(π_2)$ starts.  Then $π_1$ is contained in
some $h_r$ when $\UniversalApply(π_1)$ finishes, and since $π_2$
can only enter $h$ by being appended at the end, we get $π_1$
linearized before $π_2$.

Finally, we need to show termination.  The algorithm is written with
a loop, so in principle it could run forever.  But we can argue that
no process after executes the loop more than twice.
The reason is that a process $p$ puts its operation in $\UniversalOp[p]$ before it
calculates $r$; so any process that writes $r' > r$ to sees $p$'s operation before the next round.  It follows that $p$'s
value gets included in the history no later than round $r+2$.
(We'll see this sort of thing again when we do atomic snapshots in
Chapter <ref>.)

Building a consistent shared history is easier with some particular
objects that solve consensus.  For example, a fetch-and-cons
object that supplies an operation that pushes a new head onto a linked
list and returns the old head trivially implements the common history
above without the need for helping.  One way to implement
fetch-and-cons is with memory-to-memory swap; to add a new element to the
list, create a cell with its next pointer pointing to
itself, then swap the next field with the head
pointer for the entire list.

The solutions we've described here have a number of deficiencies that
make them impractical in a real system (even more so than many of the
algorithms we've described).  If we store entire histories in a
register, the register will need to be very, very wide.  If we store
entire histories as a linked list, it will take an unbounded amount of
time to read the list.  For solutions to these problems, see
<cit.> or the papers of Herlihy [153] and
Plotkin [204].

Atomic snapshots2020

We've seen in the previous chapter that there are a lot of things we
can't make wait-free with just registers.  But there are a lot of
things we can.  Atomic snapshots are a tool that let us do a lot of
these things easily.

atomic snapshot object acts like a collection of $n$
single-writer multi-reader atomic registers with a special
snapshot operation that returns (what appears to be) the
state of all $n$ registers at the same time.  This is easy without failures: we simply lock the whole register file, read them all, and unlock them to let all the starving writers in.  But it gets harder if we want a protocol that is wait-free, where any process can finish its own snapshot or write even if all the others lock up.

We'll give the usual sketchy description of a couple of snapshot
algorithms.  More details on early snapshot results can be found in <cit.>
or <cit.>.  There is also a
reasonably recent survey by Fich on upper and lower
bounds for the problem [121].

§ THE BASIC TRICK: TWO IDENTICAL COLLECTS EQUALS A SNAPSHOT

Let's tag any value written with a sequence number, so that each value
written has a field attached to it that increases over time.
We can now detect if a new write has occurred between two reads of the
same variable.  Suppose now that we repeatedly perform
collectcollects—reads of all $n$ registers—until
two successive collects return exactly the same vector of values and
sequence numbers.  We can then conclude that precisely these values
were present in the registers at some time in between the two
collects.  This gives us a very simple algorithm for
Unfortunately, it doesn't terminate if there are a lot of writers
around.[This isn't always a problem, since there may be
external factors that keep the writers from showing up too much.
Maurice Herlihy and I got away with using exactly this snapshot
algorithm in an ancient, pre-snapshot paper on randomized
consensus [38].  The reread-until-no-change idea
was used as early as 1977 by Lamport [174].]
So we need some way to slow the writers down, or at least get them to do snapshots for us.

§ SNAPSHOTS USING DOUBLE COLLECTS WITH HELPING

This is the approach taken by Afek and his five illustrious
co-authors [9] (see also
<cit.> or
<cit.>): before a process can write to its
register, it first has to complete a snapshot and leave the results
behind with its write.[The algorithm is usually called the
AADGMS algorithm by people who can remember all the names—or at
least the initials—of the
team of superheroes who came up with it (Afek, Attiya, Dolev, Gafni,
Merritt, and Shavit).
Historically, this was one of three
independent solutions to the problem that appeared at about the same
time.  A
similar algorithm for
composite registercomposite registers
was given by James Anderson [54]
and a somewhat different algorithm for consistent scan was
given by Aspnes and Herlihy [39].  The
Afek  algorithm had the advantage of using bounded registers (in
its full version), and so it and its name for atomic snapshot
prevailed over its competitors.]
This means that if some slow process (including a slow writer, since now writers need to do snapshots too) is prevented from doing the two-collect snapshot because too much writing is going on, eventually it can just grab and return some pre-packaged snapshot gathered by one of the many successful writers.

Specifically, if a process executing a single snapshot operation $σ$ sees
values written by a single process $i$ with three different sequence
numbers $s_{1}$, $s_{2}$ and $s_3$, then it can be assured that the
snapshot $σ_3$ gathered with sequence number $s_{3}$ started no
earlier than $s_{2}$ was written (and thus no earlier than
$σ$ started, since $σ$ read $s_{1}$ after it started)
and ended no later than $σ$ ended (because $σ$ saw it).
It follows that the snapshot can safely return
$σ_3$, since that
represents the value of the registers at
some time inside $σ_3$'s interval, which is contained
completely within $σ$'s interval.

So a snapshot repeatedly does collects until either (a) it gets two
identical collects, in which case it can return the results (a
direct scan, or (b) it
sees three different values from the same process, in which case it
can take the snapshot collected by the second write (an
indirect scan).  See pseudocode in
Algorithm <ref>.

despite the fact that updates keep coming and
everybody is trying to do snapshots all the
time, a snapshot operation of a single process is guaranteed to
terminate after at most $n+1$ collects.  The reason is that in order
to prevent case (a) from holding, the adversary has to supply at least
one new value in each collect after the first.  But it can only supply
one new value for each of the $n-1$ processes that aren't doing
collects before case (b) is triggered (it's triggered by the first
process that shows up with a second new value).  Adding up all the collects
gives $1 + (n-1) + 1 = n+1$ collects before one of the cases holds.
Since each collect takes $n-1$ read operations (assuming the process
is smart enough not to read its own register), a snapshot operation
terminates after at most $n^{2}-1$ reads.

$s ← \Scan(A)$
$A[i] ← \Tuple{A[i].\AADGMScount + 1, v, s}$

$\AADGMSinitial ← \Collect(A)$
$\AADGMSprevious ← \AADGMSinitial$

$s ← \Scan(A)$
$s = \AADGMSprevious$
Two identical collects

$∃j: s[j].\AADGMScount ≥
\AADGMSinitial[j].\AADGMScount + 2$
Three different counts from $j$

Nothing useful, try again
$\AADGMSprevious ← s$

Snapshot of [9] using unbounded registers

For a write operation, a process first performs a snapshot, then
writes the new value, the new sequence number, and the result of the
snapshot to its register (these are very wide registers).  The total
cost is $n^{2}-1$ read operations for the snapshot plus $1$ write

§.§ Linearizability

We now need to argue that the snapshot vectors returned by the
Afek  algorithm really work, that is, that between each matching
invoke-snapshot and respond-snapshot there was some
actual time where the registers in the array contained precisely the
values returned in the respond-snapshot action.  We do so by assigning
a linearization point to each snapshot vector, a time at
which it appears in the registers (which for correctness of the
protocol had better lie within the interval between the snapshot
invocation and response).  For snapshots obtained through case (a),
take any time between the two collects.  For snapshots obtained
through case (b), take the linearization point already assigned to the
snapshot vector provided by the third write.  In the latter case we
argue by induction on termination times that the linearization point lies inside the snapshot's interval.

Note that this means that all snapshots were ultimately collected by
two successive collects returning identical values, since any case-(b)
snapshot sits on top of a finite regression of case-(b) snapshots that
must end with a case-(a) snapshot. This means that any snapshot
corresponds to an actual global state of the registers at some point
in the execution, which is not true of all snapshot algorithms. It
also means that we can replace the registers in the snapshot array
with other objects that allow us to detect updates (say, counters or
max registers) and still get snapshots.

In an actual execution, the fact that we are waiting for double
collects with no intervening updates means that if there are many
writers, eventually all of them will stall waiting for a case-(a)
snapshot to complete. So that snapshot will complete because all the
writers are stuck. In a sense, requiring writers to do
snapshots first almost gives us a form of locking, but without the
vulnerability to failures of a real lock.

§.§ Using bounded registers

The simple version of the Afek  algorithm requires unbounded
registers (since sequence numbers may grow forever).  One of the
reasons why this algorithm required so many smart people was to get
rid of this assumption: the paper describes a (rather elaborate)
mechanism for recycling sequence numbers that prevents unbounded
growth (see also <cit.>).  In practice, unbounded registers are probably not really an issue once one has accepted very large registers, but getting rid of them is an interesting theoretical problem.

It turns out that with a little cleverness we can drop the sequence
numbers entirely.  The idea is that we just need a mechanism to detect
when somebody has done a lot of writes while a snapshot is in
progress.  A naive approach would be to have sequence numbers wrap
around mod $m$ for some small constant modulus $m$; this fails because
if enough snapshots happen between two of my collects, I may notice
none of them because all the sequence numbers wrapped around all the
way.  But we can augment mod-$m$ sequence numbers with a second handshaking mechanism that detects when a large enough number of snapshots have occurred; this acts like the guard bit on an automobile odometer, than signals when the odometer has overflowed to prevent odometer fraud by just running the odometer forward an extra million miles or so.

The result is the full version of Afek  [9].
(Our presentation here
follows <cit.>.)  The key mechanism for detecting
odometer fraud is a handshake, a pair of single-writer bits
used by two processes to signal each other that they have done
something.  Call the processes $S$ (for same) and $D$ (for
different), and supposed we have handshake bits $h_{S}$ and
$h_{D}$.  We then provide operations
(signal that something is happening) and (check if something happened) for each process; these operations are asymmetric.  The code is:

$\TryHandshake(S)$: $h_{S} ← h_{D}$ (make the two bits the same)

$\TryHandshake(D)$: $h_{D} ← ¬{}h_{S}$ (make the two bits different)

$\CheckHandshake(S)$: return $h_{S} ≠ h_{D}$ (return true if D changed its bit)

$\CheckHandshake(D)$: return $h_{S} = h_{D}$ (return true if S changed its bit)

The intent is that returns true if the other process
called after I did.  The situation is a bit messy,
however, since involves two register operations (reading
the other bit and then writing my own).  So in fact we have to look at
the ordering of these read and write events.  Let's assume that
is called by $S$ (so it returns true if and only if it sees different values).  Then we have two cases:

* $\CheckHandshake(S)$ returns true.  Then $S$ reads a different
value in $h_{D}$ from the value it read during its previous call to
$\TryHandshake(S)$.  It follows that $D$ executed a write as part of a
$\TryHandshake(D)$ operation in between $S$'s previous read and its current read.

* $\CheckHandshake(S)$ returns false.  Then $S$ reads the same
value in $h_{D}$ as it read previously.  This does not necessarily
mean that $D$ didn't write $h_{D}$ during this interval—it is
possible that $D$ is just very out of date, and did a write that
didn't change the register value—but it does mean that $D$ didn't
perform both a read and a write since $S$'s previous read.

How do we use this in a snapshot algorithm?  The idea is that before
performing my two collects, I will execute on my end of
a pair of handshake bits for every other process.  After performing my
two collects, I'll execute .  I will also assume each
update (after performing a snapshot) toggles a mod-2 sequence number
bit on the value stored in its segment of the snapshot array.  The
hope is that between the toggle and the handshake, I detect any
changes.  (See <cit.> for the actual code.)

Does this work?  Let's look at cases:

* The toggle bit for some process $q$ is unchanged between the
two snapshots taken by $p$.  Since the bit is toggled with each
update, this means that an even number of updates to $q's$ segment
occurred during the interval between $p$'s writes.  If this even
number is 0, we are happy: no updates means no call to by $q$, which means we don't see any change in $q$'s segment, which
is good, because there wasn't any.  If this even number is 2 or more,
then we observe that each of these events precedes the following one:

* $p$'s call to .

* $p$'s first read.

* $q$'s first write.

* $q$'s call to at the start of its second scan.

* $q$'s second write.

* $p$'s second read.

* $p$'s call to .

It follows that $q$ both reads and writes the handshake bits in
between $p$'s calls to and , so $p$
correctly sees that $q$ has updated its segment.

* The toggle bit for $q$ has changed.  Then $q$ did an odd number
of updates (i.e., at least one), and $p$ correctly detects this fact.

What does $p$ do with this information?  Each time it sees that $q$
has done a scan, it updates a count for $q$.  If the count reaches 3,
then $p$ can determine that $q$'s last scanned value is from a scan
that is contained completely within the time interval of $p$'s scan.
Either this is a scan!directdirect scan, where $q$
actually performs two collects with no changes between them, or it's
an scan!indirectindirect scan, where $q$ got its
value from some other scan completely contained within $q$'s scan.  In
the first case $p$ is immediately happy; in the second, we observe
that this other scan is also contained within the interval of $p$'s
scan, and so (after chasing down a chain of at most $n-1$ indirect
scans) we eventually reach a direct scan contained within it that
provided the actual value.  In either case $p$ returns the value of pair of adjacent collects with no changes between them that occurred during the execution of its scan operation, which gives us linearizability.

§ FASTER SNAPSHOTS USING LATTICE AGREEMENT

The Afek  algorithm and its contemporaries all require $O(n^2)$
operations for each snapshot.  It is possible to get this bound down
to $O(n)$ using a more clever algorithm, [164] which is the best we can
reasonably hope for in the worst case given that (a) even a collect (which doesn't guarantee
anything about linearizability) requires $Θ(n)$
operations when implemented in the obvious way, and (b) there is a linear lower
bound, due to Jayanti, Tan, and Toueg [171], on a large
class of wait-free objects that includes snapshot.[But see
§<ref> for a faster alternative if we
allow either randomization or limits on the number of times the
array is updated.]

The first step, due to Attiya, Herlihy, and
Rachman [41], is a reduction to a related problem called
lattice agreement.

§.§ Lattice agreement

A lattice is a partial order in which every pair of elements
$x$, $y$ has a least upper bound $x∨{}y$ called the join
of $x$ and $y$
and a greatest lower bound $x∧{}y$ called the meet of
$x$ and $y$.  For example, we can make a lattice out of sets by
letting join be union and meet be intersection; or we can make a
lattice out of integers by making join be $\max$ and meet be $\min$.

In the lattice agreement problem, each process starts with an input
$x_{i}$ and produces an output $y_{i}$, where both are elements of some lattice.  The requirements of the problem are:

Comparabilitycomparability For all $i$, $j$, $y_{i} ≤ y_{j}$ or
$y_{j} ≤ y_{i}$.

Downward validityvalidity!downward
downward validity For all $i$, $x_{i} ≤ y_{i}$.

Upward validity
upward validity For all $i$, $y_{i} ≤

These requirements are analogous to the requirements for consensus.
Comparability acts like agreement: the views
returned by the lattice-agreement protocol are totally ordered.
Downward validity says that each process will include its own input in
its output.  Upward validity acts like validity: an output can't
include anything that didn't show up in some input.

For the snapshot algorithm, we also demand wait-freedom: each process terminates after a bounded number of its own steps, even if other processes fail.

Note that if we are really picky, we can observe that we don't
actually need meets; a semi-lattice that provides only joins
is enough.  In practice we almost always end up with a full-blown
lattice, because (a) we are working with finite sets, and (b) we
generally want to include a bottom element $⊥$ that is less than
all the other elements, to represent the “empty” state of our data
structure.  But any finite join-semi-lattice with a bottom element
turns out to be a lattice, since we can define $x ∧ y$ as the
join of all elements $z$ such that $z ≤ x$ and $z ≤ y$.  We don't
use the fact that we are in a lattice anywhere, but it does
save us two syllables not to have to say “semi-lattice agreement.”

§.§ Connection to vector clocks

The first step in reducing snapshot to lattice agreement
is to have each writer
generate a sequence of increasing timestamps $r_{1}, r_{2}, \dots{},$
and a snapshot corresponds to some vector of timestamps $\Tuple{t_{1}, t_{2}
\dots{} t_{n}}$, where $t_{i}$ indicates the most recent write by
$p_{i}$ that is included in the snapshot (in other words, we are using
vector clocks again; see §<ref>).
Now define $v≤v'$ if $v_{i}≤v'_{i}$ for all $i$; the resulting
partial order is a lattice, and in particular we can compute
$x∨{}y$ by the rule $(x∨{}y)_{i} = x_{i}∨{}y_{i}$.

Suppose now that we have a bunch of snapshots that satisfy the
comparability requirement. This means they are totally ordered.  Then we
can construct a sequential execution by ordering the snapshots in
increasing order with each update operation placed before the first
snapshot that includes it.  This sequential execution is not
necessarily a linearization of the original execution, and a single
lattice agreement object won't support more than one operation for
each process, but the idea is that we can nonetheless use lattice
agreement objects to enforce comparability between concurrent
executions of snapshot, while doing some other tricks (exploiting,
among other things, the validity properties of the lattice agreement
objects) to get linearizability over the full execution.

§.§ The full reduction

The Attiya-Herlihy-Rachman algorithm is given as
Algorithm <ref>.  It uses an array of registers
$R_{i}$ to hold round numbers (timestamps); an array $S_{i}$ to hold
values to scan; an unboundedly humongous array $V_{ir}$ to hold views
obtained by each process in some round; and a collection of
lattice-agreement objects $\LALA_r$, one for each round.

$\DataSty{attempt} ← 1$ $2$
$R_{i} ← r ← \max(R_{1}\dots{}R_{n}; R_{i}+1)$
$\LACollect ← \Read(S_{1}\dots{}S_{n})$
$\LAView ← \LALA_r(\LACollect)$
max computation requires a collect
$\max(R_{1}\dots{}R_{n}) ≤ R_{i}$line-LA-check
$V_{ir} ← \LAView$

finding nonempty $V_{jr}$ also requires a collect
$V_{ir} ←$ some nonempty $V_{jr}$

Lattice agreement snapshot

The algorithm makes two attempts to obtain a snapshot.  In both cases,
the algorithm advances to the most recent round it sees (or its
previous round plus one, if nobody else has reached this round yet),
attempts a collect, and then runs lattice-agreement to try to get a
consistent view.  If after getting its first view it finds that some
other process has already advanced to a later round, it makes a second
attempt at a new, higher round $r'$ and uses some view that it obtains in this second round, either directly from lattice agreement, or (if it discovers that it has again fallen behind), it uses an indirect view from some speedier process.

The reason why I throw away my view if I find out you have advanced to
a later round is not because the view is bad for me but because it's
bad for you: I might have included some late values in my view that you
didn't see, breaking consistency between rounds.  But I don't have to
do this more than once; if the same thing happens on my second
attempt, I can use an indirect view as in [9],
knowing that it is safe to do so because any collect that went into
this indirect view started after I did.

The update operation is the usual update-and-scan procedure; for
completeness this is given as
Algorithm <ref>.  To make it easier to
reason about the algorithm, we assume that an update returns the
result of the embedded scan.

$S_{i} ← (S_{i}.\SeqNo + 1, v)$

Update for lattice agreement snapshot

§.§ Why this works

We need to show three facts:

* All views returned by the scan operation are comparable; that is, there exists a total order on the set of views (which can be extended to a total order on scan operations by breaking ties using the execution order).

* The view returned by an update operation includes the update (this implies that future views will also include the update, giving the correct behavior for snapshot).

* The total order on views respects the execution order: if
$π_1$ and $π_2$ are scan operations that return $v_1$ and $v_2$,
$π_{1} <_{S} π_{2}$ implies $v_{1} ≤ v_{2}$.  (This gives us linearization.)

Let's start with comparability.  First observe that any view returned
is either a direct view (obtained from $\LALA_r)$ or an indirect view
(obtained from $V_{jr}$ for some other process $j$).  In the latter
case, following the chain of indirect views eventually reaches some
direct view.  So all views returned for a given round are ultimately
outputs of $\LALA_r$ and thus satisfy comparability.

But what happens with views from different rounds?  The
lattice-agreement objects only operate within each round, so we need
to ensure that any view returned in round $r$ is included in any
subsequent rounds.  This is where checking round numbers after calling
$\LALA_r$ comes in.

Suppose some process $i$ returns a direct view; that is, it sees no
higher round number in either its first attempt or its
second attempt.  Then at the time it starts checking the round number
in Line <ref>, no process
has yet written a round number higher than the round number of $i$'s
view (otherwise $i$ would have seen it).  So no process with a higher
round number has yet executed the corresponding collect operation.
When such a process does so, it obtains values that are at least as
large as
those fed into $\LALA_r$, and $i$'s round-$r$ view is less than or equal to
the vector of these values by upward validity of $\LALA_r$, and thus less
than or equal to the vector of values returned by $LA_{r'}$ for $r' >
r$, by
downward validity of $\LALA_{r'}$.  So we have comparability of all direct views, which
implies comparability of all indirect views as well.

To show that each view returned by a scan includes any preceding update, we observe that either a process returns its first-try scan (which includes the update by downward validity) or it returns the results of a scan in the second-try round (which includes the update by downward validity in the later round, since any collect in the second-try round starts after the update occurs).  So no updates are missed.

Now let's consider two scan operations $π_1$ and $π_2$ where $π_{1}$ precedes
$π_{2}$ in the execution.  We want to show that, for the
views $v_1$ and $v_2$ that these scans return, $v_{1} ≤
v_{2}$. Pick some time between when $π_1$ finishes and $π_2$ starts,
and let $s$ be the contents of the registers at this time. Then $v_1
≤ s$ by upward validity, since any input fed to a lattice agreement
object before $π_1$ finishes was collected from a register whose value
was no greater than it is in $s$. Similarly, $s ≤ v_2$ by downward
validity, because $v_2$ is at least as large as the $\LACollect$ value
read by $π_2$, and this is at least as large as $s$. So $v_1 ≤ s ≤

§.§ Implementing lattice agreement

There are several known algorithms for implementing lattice
agreement, including the original algorithm of Attiya, Herlihy, and
Rachman [41] and an adaptive algorithm of Attiya and
Fouren [30].
The best of them (assuming multi-writer registers) is Inoue 's
linear-time lattice agreement protocol [164].

The intuition behind this protocol is to implement lattice agreement using divide-and-conquer.  The processes are organized into a tree, with each leaf in the tree corresponding to some process's input.  Internal nodes of the tree hold data structures that will report increasingly large subsets of the inputs under them as they become available.  At each internal node, a double-collect snapshot is used to ensure that the value stored at that node is always the union of two values that appear in its children at the same time.  This is used to guarantee that, so long as each child stores an increasing sequence of sets of inputs, the parent does so also.

Each process ascends the tree updating nodes as it goes to ensure that
its value is included in the final result.  A clever data
structure is used to ensure that out-of-date smaller sets don't
overwrite larger ones at any node, and the cost of using this data
structure and carrying out the double-collect snapshot at a node with
$m$ leaves below it is shown to be $O(m)$.  So the total cost of a
snapshot is $O(n + n/2 + n/4 + \dots{} 1) = O(n)$, giving the linear time bound.

Let's now look at the details of this protocol.  There are two main
components: the algorithm used to compute a new value for each node of the tree, and the and operations used to store the data in the node.  These are both rather specialized algorithms and depend on the details of the other, so it is not trivial to describe them in isolation from each other; but with a little effort we can describe exactly what each component demands from the other, and show that it gets it.

The algorithm does the usual two-collects-without change
trick to get the values of the children and then stores the result.
In slightly more detail:

* Perform on both children.  This returns a set of leaf values.

* Perform on both children again.

* If the values obtained are the same in both collects, call on the current node to store the union of the two sets and proceed to the parent node.  Otherwise repeat the preceding step.

The requirement of the algorithm is that calling on a
given node returns a non-decreasing sequence of sets of values; that
is, if returns some set $S$ at a particular time and later
returns $S'$, then $S\subseteq{}S'$.  We also require that the set
returned by is a superset of any set written by a that precedes it, and that it is equal to some such set.  This last property only works if we guarantee that the values stored by are all comparable (which is shown by induction on the behavior of at lower levels of the tree).

Suppose that all these conditions hold; we want to show that the
values written by successive calls to are all comparable, that
is, for any values $S$, $S'$ written by union we have $S\subseteq{}S'$
or $S'\subseteq{}S$.  Observe that $S = L\cup{}R$ and $S' =
L'\cup{}R'$ where $L$, $R$ and $L'$, $R'$ are sets read from the
children.  Suppose that the operation producing $S$ completes
its snapshot before the operation producing $S'$.  Then
$L\subseteq{}L'$ (by the induction hypothesis) and $R\subseteq{}R'$,
giving $S\subseteq{}S'$.

We now show how to implement the and operations.  The
main thing we want to avoid is the possibility that some large set
gets overwritten by a smaller, older one.
The solution is to have $m$
registers $a[1\dots m]$, and write a set of size $s$ to every register
in $a[1\dots s]$ (each register gets a copy of the entire set).
Because register $a[s]$ gets only sets of size $s$ or larger, there is no possibility that our set is overwritten by a smaller one.
If we are clever about how we organize this, we can guarantee that the
total cost of all calls to by a particular process is
$O(m)$, as is the cost of the single call to in

Pseudocode for both is given as Algorithm <ref>.  This is a
simplified version of the original algorithm from [164],
which does the writes in increasing order and thus forces readers
to finish incomplete writes that they observe, as in
Attiya-Bar-Noy-Dolev [18] (see also
Chapter <ref>).

array $a[1\dots m]$ of sets, initially $\emptyset$
index $p$, initially $0$
$i ← \card*{S}$ $1$
$a[i] ← S$

update $p$ to last nonempty position
$s ← a[p]$
$p = m$ $a[p+1] = \emptyset$

$p ← p+1$

Increasing set data structure

Naively, one might think that we could just write directly to
and skip the previous ones, but this makes it harder for a reader to
detect that $a[\card*{S}]$ is occupied.  By writing all the previous
registers, we make it easy to tell if there is a set of size $\card*{S}$ or
bigger in the sequence, and so a reader can start at the beginning and
scan forward until it reaches an empty register, secure in the
knowledge that no larger value has been written.[This trick
of reading in one direction and writing in another dates back to a
paper by Lamport from 1977 [174].]  Since we want to
guarantee that no reader every spends more that $O(m)$ operations on
an array of $m$ registers (even if it does multiple calls to
), we also have it remember the last location read in
each call to and start there again on its next call.
For , because we only call it once, we don't have to be
so clever, and can just have it write all $\card*{S} ≤ m$ registers.

We need to show linearizability.
We'll do so by assigning a specific linearization point to each
high-level operation.  Linearize each call to at
the last time that it reads $a[p]$.  Linearize each call to
$\InoueWriteSet(S)$ at the first time at which $a[\card*{S}] = S$ and
$a[i] \ne \emptyset$ for every $i < \card*{S}$ (in other words, at the
first time that some reader might be able to find and return $S$); if
there is no such time, linearize the call at the time at which it
returns.  Since every linearization point is inside its call's
interval, this gives a linearization that is consistent with the
actual execution.  But we have to argue that it is also consistent
with a sequential execution, which means that we need to show that
every operation returns the largest set among those whose
corresponding operations are linearized earlier.

Let $R$ be a call to and $W$ a call to
If $R$ returns $S$, then at the time that $R$ reads $S$ from
$a[\card*{S}]$, we have that (a) every register $a[i]$ with $i <
\card*{S}$ is non-empty (otherwise $R$ would have stopped earlier), and
(b) $\card*{S} = m$ or $a[\card*{S}+1] = \emptyset$ (as otherwise $R$
would have kept going after later reading $a[\card*{S}+1]$.
From the rule for when calls are linearized, we see
that the linearization point of $W$ precedes this time and that the
linearization point of any call to with a larger set
follows it.  So the return value of $R$ is consistent.

The payoff: unless we do more updates than snapshots, don't want to
assume multi-writer registers, are worried about unbounded space,
have a beef with huge registers, or care about constant factors, it
costs no more time to do a snapshot than a collect.
So in theory we can get away with assuming snapshots pretty much wherever we need them.

§ PRACTICAL SNAPSHOTS USING LL/SC

Though atomic registers are enough for snapshots, it is possible to
get a much more efficient snapshot algorithm using stronger
synchronization primitives.  An algorithm of Riany, Shavit, and
Touitou [214] uses
load-linked/store-conditional objects to build an atomic snapshot protocol with linear-time snapshots and constant-time updates using small registers.  We'll give a sketch of this algorithm here.

The RST algorithm involves two basic ideas: the first is a snapshot
algorithm for a single scanner (i.e., only one process can do
snapshots) in which each updater maintains two copies of its segment,
a copy (that may be more recent than the current scan) and a
copy (that is guaranteed to be no more recent than the current scan).  The idea is that when a scan is in progress, updaters ensure that the values in memory at the start of the scan are not overwritten before the scan is completed, by copying them to the low registers, while the high registers allow new values to be written without waiting for the scan to complete.  Unbounded sequence numbers, generated by the scanner, are used to tell which values are recent or not.

As long as there is only one scanner, nothing needs to be done to
ensure that all scans are consistent, and indeed the single-scanner
algorithm can be implemented using only atomic registers.  But extending the algorithm to
multiple scanners is tricky.  A simple approach would be to keep a
separate low register for each concurrent scan—however, this would
require up to $n$ low registers and greatly increase the cost of an
update.  Instead, the authors devise a mechanism, called a
collect!coordinatedcoordinated collect, that allows
the scanners collectively to implement a sequence of virtual
scans that do not overlap.  Each virtual scan is implemented using
the single-scanner algorithm, with its output written to a common
view array that is protected from inconsistent updates using
LL/SC operations (CAS also works).  A scanner participates in virtual scans until it obtains a virtual scan that is useful to it (this means that the virtual scan has to take place entirely within the interval of the process's actual scan operation); the simplest way to arrange this is to have each scanner perform two virtual scans and return the value obtained by the second one.

The paper puts a fair bit of work into ensuring that only $O(n)$ view arrays are needed, which requires handling some extra special cases where particularly slow processes don't manage to grab a view before it is reallocated for a later virtual scan.  We avoid this complication by simply assuming an unbounded collection of view arrays; see the paper for how to do this right.

A  more recent
paper by Fatourou and Kallimanis [123] gives improved time and space complexity using the same basic technique.

§.§ Details of the single-scanner snapshot

The single-scanner snapshot is implemented using a shared variable (incremented by the scanner but used by all processes) and an
array of n snapshot segments, each of which is divided into a
and component consisting of a value and a timestamp.
Initially, is 0, and all memory locations are initialized to
$(⊥, 0)$.  This part of the algorithm does not require LL/SC.

A call to  copies the first of $\RSTmem[j].\RSThigh$ or
$\RSTmem[j].\RSTlow$ that has a sequence number less than the current
sequence number.  Pseudocode is given as Algorithm <ref>.

$\RSTcurrSeq ← \RSTcurrSeq + 1$
$j ← 0$ $n-1$
$h ← \RSTmem[j].\RSThigh$
$h.\RSTseq < \RSTcurrSeq$
$\RSTview[j] ← h.\RSTvalue$

$\RSTview[j] ← \RSTmem[j].\RSTlow.\RSTvalue$

Single-scanner snapshot: scan

The operation for process $i$ cooperates by copying
$\RSTmem[i].\RSThigh$ to $\RSTmem[i].\RSTlow$ if it's old.

The  operation always writes its value to
$\RSTmem[i].\RSThigh$, but preserves the previous value in
$\RSTmem[i].\RSTlow$ if its sequence number indicates that it may have
been present at the start of the most recent call to .
This means that $\RSTscan$ can get the old value if the new value is
too recent.
is given in Algorithm <ref>.

$\RSTseq ← \RSTcurrSeq$
$h ← \RSTmem[i].\RSThigh$
$h.\RSTseq \ne \RSTseq$
$\RSTmem[i].\RSTlow ← h$

$\RSTmem[i].\RSThigh ← (\RSTvalue, \RSTseq)$

Single-scanner snapshot: update

To show this actually works, we need to show that there is a
linearization of the scans and updates that has each scan return
precisely those values whose corresponding updates are linearized
before it.  The ordering is based on when each operation $S$
increments and when each  operation $U$ reads it; specifically:

* If $U$ reads after $S$ increments it, then $S < U$.

* If $U$ reads before $S$ increments it and $S$ reads
$\RSTmem[i].\RSThigh$ (where $i$ is the process carrying out $U$)
before $U$ writes it, then $S < U$.

* If $U$ reads before $S$ increments it, but $S$ reads
$\RSTmem[i].\RSThigh$ after $U$ writes it, then $U < S$.

Updates are ordered based on intervening scans (i.e., $U_1 < U_2$ if
$U_1<S$ and $S<U_2$ by the above rules), or by the order in which they read if there is no intervening scan.

To show this is a linearization, we need first to show that it extends
the ordering between operations in the original schedule.  Each of the
above rules has $π_1 < π_2$ only if some low-level operation of
$π_1$ precedes some low-level operation of $π_2$, with the
exception of the transitive ordering of two update events with an
intervening scan.  But in this last case we observe that if $U_1<S$,
then $U_1$ writes $\RSTmem[i].\RSThigh$ before $S$ reads it, so if
$U_1$ precedes $U_2$ in the actual execution, $U_2$ must write
$\RSTmem[i].\RSThigh$ after $S$ reads it, implying $S<U_2$.

Now we show that the values returned by are consistent with
the linearization ordering; that, is, for each $i$, copies to
$\RSTview[i]$ the value in the last by process $i$ in the
linearization.   Examining the code for , we see that a
operation $S$ takes $\RSTmem[i].\RSThigh$ if its sequence
number is less than $\RSTcurrSeq$, i.e., if the operation $U$
that wrote it read before $S$ incremented it and wrote
$\RSTmem[i].\RSThigh$ before $S$ read it; this gives $U<S$.
Alternatively, if takes $\RSTmem[i].\RSTlow$, then
$\RSTmem[i].\RSTlow$ was copied by some update operation $U'$ from the
value written to $\RSTmem[i].\RSThigh$ by some update $U$ that read
before $S$ incremented it.  Here $U'$ must have written
$\RSTmem[i].\RSThigh$ before $S$ read it (otherwise $S$ would have
taken the old value left by $U$) and since $U$ precedes $U'$ (being an
operation of the same process) it must therefor also have written
$\RSTmem[i].\RSThigh$ before $S$ read it.  So again we get the first
case of the linearization ordering and $U<S$.

So far we have shown only that $S$ obtains values that were linearized
before it, but not that it ignores values that were linearized after
it.  So now let's consider some $U$ with $S < U$.  Then one of two cases holds:

* $U$ reads after $S$ increments it.  Then $U$ writes a
sequence number in $\RSTmem[i].\RSThigh$ that is greater than or equal to
the value used by $S$; so $S$ returns $\RSTmem[i].\RSTlow$
instead, which can't have a sequence number equal to and thus
can't be $U$'s value either.

* $U$ reads before $S$ increments it but writes
$\RSTmem[i].\RSThigh$ after $S$ reads it.  Now $S$ won't return $U$'s
value from $\RSTmem[i].\RSThigh$ (it didn't read it), and won't get
it from $\RSTmem[i].\RSTlow$ either (because the value that is
in $\RSTmem[i].\RSThigh$ will have $\DataSty{seq} < \RSTcurrSeq$, and so
$S$ will take that instead).

So in either case, if $S<U$, then $S$ doesn't return $U$'s value.  This concludes the proof of correctness.

§.§ Extension to multiple scanners

See the paper for details.

The essential idea: now represents a virtual scan
$\RSTview_{r}$ generated cooperatively by all the scanners working
together in some asynchronous round $r$.  To avoid conflicts, we
update $\RSTview_{r}$ using LL/SC or compare-and-swap (so that only
the first scanner to write wins), and pretend that reads of
$\RSTmem[i]$ by losers didn't happen.  When $\RSTview_{r}$ is full,
start a new virtual scan and advance to the next round (and thus the
next $\RSTview_{r+1}$).

§ APPLICATIONS

Here we describe a few things we can do with snapshots.

§.§ Multi-writer registers from single-writer registers

One application of atomic snapshot is building multi-writer registers
from single-writer registers.  The idea is straightforward: to perform
a write, a process does a snapshot to obtain the maximum sequence
number, tags its own value with this sequence number plus one, and
then writes it.  A read consists of a snapshot followed by returning
the value associated with the largest sequence number (breaking ties
by process id).  (See <cit.> for a proof that this
actually works.)  This requires using a snapshot that doesn't use
multi-writer registers, and turns out to be overkill in practice; there are
simpler algorithms that give $O(n)$ cost for reads and writes based on
timestamps (see <cit.>).

With additional work, it is even possible to eliminate the requirement
of multi-reader registers, and get a simulation of multi-writer
multi-reader registers that goes all the way down to single-writer
single-read registers, or even single-writer single-reader bits.  See
<cit.> or <cit.> for details.

§.§ Counters

Given atomic snapshots, it's easy to build a counter (supporting
increment, decrement, and read operations); or, in more generality, a
generalized counter (supporting increments by arbitrary amounts); or, in even
more generality, an object supporting any collection of commutative
and associative
update operations (as long as these operations don't return anything).  The idea is that each process stores in its segment the total of all operations it has performed so far, and a read operation is implemented using a snapshot followed by summing the results.  This is a case where it is reasonable to consider multi-writer registers in building the snapshot implementation, because there is not necessarily any circularity in doing so.

§.§ Resilient snapshot objects

The previous examples can be generalized to objects with operations
that either read the current state of the object but don't update it
or update the state but return nothing, provided the update operations
either overwrite each other (so that $Cxy = Cy$ or $Cyx = Cx$) or
commute (so that $Cxy = Cyx$).

This was shown by Aspnes and
Herlihy [39] and improved on by Anderson and
Moir [49] by eliminating unbounded space usage.
Anderson and Moir
also defined the terms
object!snapshotsnapshot objectsnapshot
objects for those with separate read and update operations and
resilient object
resilience for the property that all operations commute or
The basic idea underneath both of these papers is to use the
multi-writer register construction given above, but break ties among
operations with the same sequence numbers by first placing overwritten
operations before overwriting operations and only then using process

This almost shows that snapshots can implement any object with
consensus number 1 where update operations return nothing, because an
object that is not resilient violates the commute-or-overwrite condition in some
configuration has consensus number at least 2 (see
§<ref>)—in Herlihy's terminology,
non-resilient objects have interfering operations.  It doesn't quite work (as
observed in the Anderson-Moir paper), because the tie-breaking
procedure assumes a static ordering on which operations overwrite each
other, so that given
operations $x$ and $y$ where $y$ overwrites $x$, $y$ overwrites $x$ in
any configuration.  But there may be objects with a dynamic
ordering to how operations interfere, where $y$ overwrites $x$ in some configuration, $x$
overwrites $y$ in another, and perhaps even the two operations commute
in yet another.  This prevents us from achieving consensus, but also
breaks the tie-breaking technique.  So it may be possible that there
are objects with consensus number 1 and no-return updates
that we still can't implement using only

Lower bounds on perturbable objects2020

Being able to do snapshots in linear time means that we can build
linearizable counters, generalized counters, max registers, and so on, in
linear time, by having each reader take a snapshot and combine the
contributions of each updater using the appropriate commutative and
associative operation.  A natural question is whether we can do better
by exploiting the particular features of these objects.

Unfortunately, the Jayanti-Tan-Toueg [171] lower bound for
perturbable objects says each of these objects requires
$n-1$ space and $n-1$ steps for a read operation in the worst case,
for any solo-terminating deterministic implementation from historyless
objects.  Like Burns-Lynch, this is a worst-case bound based on a
covering argument, so it may be possible to evade it in some cases
using either randomization or a restriction on the length of an
execution (see Chapter <ref>).

Perturbable means that the object has a particular property that makes the proof work, essentially that the outcome of certain special executions can be changed by stuffing lots of extra update operations in the middle (see below for details).

solo termination
solo-terminatingSolo-terminating means that a process finishes its current operation in a finite number of steps if no other process takes steps in between; it is a much weaker condition, for example, than wait-freedom.

historyless objectHistoryless objects are those for
which any operation either never changes the state (like a read, but
it could be weaker) or always sets the state to a value that depends
only on the operation and not the previous value (like a write, but it
may also return some information about the old state).  The point of
historyless objects is that covering arguments work for them: if there
is a process with a pending update operations on some object, the
adversary can use it at any time to wipe out the state of the object
and hide any previous operations from any process except the updater
(who, in a typical covering argument, is quietly killed to keep it
from telling anybody what it saw).

registers are a common example of a historyless object: the read never
changes the state, and the write always replaces it.
swap objectSwap objects (with a swap operation that
writes a new state while returning the old state) are the canonical
example, since they can implement any other historyless object (and
even have consensus number 2, showing that even extra consensus power doesn't necessarily help here).
Test-and-sets (which are basically one-bit swap objects where you can
only swap in $1$) are also historyless.  In contrast, anything that
looks like a counter or similar object where the new state is a
combination of the old state and the operation is not
historyless.   This is important because many of these objects turn out
to be perturbable, and if they were also historyless, we'd get a

Below is a sketch of the proof.  See the original
paper [171] for more details.

The basic idea is to build a sequence of executions of the form $Λ_{k}Σ_{k}π$,
where $Λ_{k}$ is a preamble consisting of various complete
update operations and $k$ incomplete update operations by processes
$p_1$ through $p_{n-1}$,
$Σ_{k}$ delivers $k$ delayed writes from the incomplete
operations in $Λ_{k},$ and $π$ is a read operation by $p_n$.
To make our life easier, we'll assume that $π$ performs only read
steps.[The idea is that if $π$ does anything else, then the
return values of other steps can be simulated by doing a $\Read$
in place of the first step and using the property of being historyless
to compute the return values of subsequent steps.  There is still a
possible objection
that we might have some historyless objects that don't even provide
$\Read$ steps.
The easiest way to work around this is to assume that our objects do
in fact provide a $\Read$ step, because taking the $\Read$
step away isn't going to make implementing the candidate
perturbable object any easier.]

We'll expand $Λ_k Σ_k$ to $Λ_{k+1} Σ_{k+1}$ by inserting new operations in between $Λ_k$ and
$Σ_k$, and argue that because those operations can change the value returned
by $π$, one of them must write an object
not covered in $Σ_k$, which will (after some more work) allow us to cover yet another object.

In order for these covered objects to keep accumulating, the reader
has to keep looking at them.
To a first approximation, this means that we want the first $k$ reads done by $π$ to
be from objects written in $Σ_k$: since the values seen by the reader
for these objects never change, the (deterministic) reader will
continue to read them even as we add more operations before $Σ_k$.  Unfortunately, this does not quite
match all possible cases, because it may be that $π$ performs useless reads of objects that aren't
covered in $Σ_k$ but that aren't written to by anybody anyway.  So we
have the more technical condition that $π$ has an initial prefix that
only includes covered reads and useless reads: formally, there is a
prefix $π'$ of $π$ that includes at least one read operation of every
object covered by $Σ_k$, such that any other read operation in $π'$
reads an object whose state cannot be
changed by any step that can be performed by any sequence of
operations by processes $p_1$ through $p_{n-1}$ that
can be inserted between $Λ_k$ and $Σ_k π$.

The induction hypothesis is that an execution $Λ_k Σ_k$ with these
properties exists for each $k ≤ n-1$.

For the base case, $Λ_{0}Σ_{0} = \Tuple{}$.  This
covers $0$ reads by $π$.

For the induction step, we start with $Λ_k Σ_k$, and look for a
sequence of operations $γ$ that we can insert in between $Λ_k$ and
$Σ_k$ that changes what $π$ returns in $Λ_k γ Σ_k π$ from what it
returned in $Λ_k γ Σ_k$.
This is where perturbability comes in: an
object is defined to be perturbable if such a sequence $γ$
always exists.

Some examples of $γ$:

* For a snapshot object, let $γ$ write to a component that is
not written to by any of the operations in $Σ_k$.

* For a max register, let $γ$ include a bigger write than all the others.

* For a counter, let $γ$ include at least $n$
increments.  The same works for a mod-$m$ counter if $m$ is at
least $2n$.
(Why $n$ increments?  With fewer increments, we can make $π$ return
the same value by being sneaky about when the partial increments
represented in $Σ_{k}$ are linearized.)

In contrast, historyless objects (including atomic registers) are not perturbable: if $Σ_{k}$ includes a write that sets the value of the object, no set of operations inserted before it will change this value.  This is good, because we know that it only takes one atomic register to implement an atomic register.

Assuming that our object is perturbable, now we want to use the
existence of $γ$ to generate our bigger execution $Λ_{k+1} Σ_{k+1}$.
As in the Burns-Lynch mutex bound [83], we will be
arguing that $γ$ must include a write to an object that is not
covered by the $k$ delayed writes.  Also as in Burns-Lynch, it turns
out that it is not enough just to delay this particular write, because
it might not cover the specific object we want.

Instead, we look for an alternative $γ'$ that changes the value of the
earliest object read by $π$ that can be changed.  We know that some
such $γ'$ exists, because $γ$ writes to some such object, so there
must be a first place in the execution of $π$ where the output of an
object can change, and there must be some $γ'$ that makes that change.
Note however that $γ'$ that hits that earliest object need not be the