Is Compare-and-Swap Really Necessary?

arXiv:1802.03844v1 [] 12 Feb 2018

Pankaj Khanchandani1 and Roger Wattenhofer1
1

ETH Zurich, Switzerland
kpankaj@ethz.ch, wattenhofer@ethz.ch

Abstract
The consensus number of a synchronization primitive, such as compare-and-swap or
fetch-and-add, is the maximum number of processes n among which binary consensus
can be solved by using read-write registers and registers supporting the synchronization primitive. As per Herlihy’s seminal result, any synchronization primitive with
consensus number n can be used to construct a wait-free and linearizable implementation of any non-trivial concurrent object or a data structure that is shared among
n processes. As the compare-and-swap primitive has infinite consensus number and is
widely supported by multi-processors, synchronization tasks have been typically solved
using the compare-and-swap synchronization primitive.
In this paper, we show that having compare-and-swap as the quintessential synchronization primitive for solving wait-free synchronization is not necessary. It is
not necessary as we give an O(1) time wait-free and linearizable implementation of
a compare-and-swap register for processes 1, 2, . . . , n using registers that support the
two weak synchronization primitives half-max and max-write, each with consensus
number one. Thus, any algorithm that uses powerful compare-and-swap registers to
solve some arbitrary synchronization problem among processes 1, 2, . . . , n can be transformed into an algorithm that has the same asymptotic time complexity and only uses
weak consensus number one primitives.

1

Introduction

Any modern multi-processor chip supports the compare-and-swap synchronization primitive which is widely used for coordination among multiple processes. The reason dates
back to 1991, when Maurice Herlihy [6] introduced consensus numbers in his seminal work
to quantify the power of a synchronization primitive. The consensus number of a synchronization primitive is defined as the maximum number of processes among which binary
consensus can be solved by using read-write registers and registers supporting the synchronization primitive. Herlihy showed that if a synchronization primitive has consensus
number n, then it can be used to design a linearizable and wait-free implementation of any
concurrent object that is shared among n processes (such as concurrent queues, stacks,
etc.). The wait-free property implies that a process completes its operation on the object
in a bounded number of steps irrespective of the schedule of the other processes. Linearizabiliy implies that each operation appears to take effect instantaneously at some point
during the execution of the operation. As the compare-and-swap primitive has infinite
consensus number, it can be used to design a linearizable and wait-free implementation
of any concurrent object. So, compare-and-swap is often considered a most powerful synchronization primitive, and as such widely supported by hardware. As a result, concurrent
algorithms and data structures have been traditionally designed using the compare-andswap primitive, eg., [11, 7, 10].
Recently, Ellen et al. [2] showed that combining two simple primitives of consensus
number one each can also achieve consensus number infinity. Thus, they showed that a set
of simple consensus number one primitives are sufficient to design a linearizable and waitfree implementation of any shared object, just like compare-and-swap is. However, this is
only a sufficiency argument and utilizes Herlihy’s universal wait-free construction of any
shared object, which is not very efficient and can take up to O(n) time per operation in a
system with n processes. This brings us to the following natural question: Is there a set of
simple (low consensus number) primitives that is not only sufficient like compare-and-swap
but also equally efficient?
One way to approach this question is to solve a specific synchronization problem with
some low consensus number primitives and compare the solution with a solution that
uses compare-and-swap. For example, Gelashvili et al. [4] implement a log data structure
using primitives of consensus number at most two, with the same performance as the log
data structure implemented using compare-and-swap. However, this approach answers the
efficiency question only partially, i.e., with respect to a specific synchronization problem.
Instead, we answer the question in affirmative for any synchronization task by giving an
O(1) time linearizable and wait-free implementation of a compare-and-swap register for
processes 1, 2, . . . , n using two consensus number one primitives that we call half-max and
max-write. Thus, we show that it is possible to transform any algorithm among processes
1, 2, . . . , n that uses compare-and-swap registers and takes O(T ) time into an O(T ) time
algorithm that only uses consensus number one primitives!
1

2

Related Work

Herlihy’s result [6] tells us that it is not possible to use low consensus number synchronization primitives to achieve higher consensus number. However, it relies on the assumption
that the individual synchronization primitives are not applied on the same register. Ellen
et al. [2] question this assumption by obtaining a higher consensus number using a collection of low consensus number primitives that are applied on the same register. One of
their examples solves binary consensus among any given number of processes using the
consensus number one primitives multiply and decrement.
This was followed by couple of works that highlight the use of combining low consensus
number primitives for specific synchronization tasks. Gelashvili et al. [4] give an efficient
implementation of a log data structure by just using low consensus number primitives.
In [9], we use some low consensus number primitives along with the compare-and-swap
√
primitive to improve the time bound of a wait-free queue from O(n) to O( n) where n
is the number of processes. Earlier, Golab et al. [5] give a blocking implementation of
comparison primitives by just using read-write registers and constant number of remote
memory references. As the implementation is blocking, it cannot be used for wait-free
synchronization tasks. So, there is no prior work that shows that a collection of low
consensus number primitives is both sufficient and efficient like compare-and-swap registers
for an arbitrary synchronization task.

3

An Overview of the Method

Our method is based on the observation that if several compare-and-swap operations attempt to simultaneously change the value in the register, only one of them succeeds. So,
instead of updating the final value of the register for each operation, we first determine the
single operation that succeeds and update the final value accordingly. This is achieved by
using two consensus number one primitives: max-write and half-max.
The max-write primitive takes two arguments. If the first argument is greater than
or equal to the value in the first half of the register, then the first half of the register is
replaced with the first argument and the second half is replaced with the second argument.
Otherwise, the register is left unchanged. This primitive helps in keeping a version number
along with a value.
The half-max primitive takes a single argument and replaces the first half of the register
with that argument if the argument is larger. Otherwise, the register remains unchanged.
This primitive is used along with the max-write primitive to determine the single successful
compare-and-swap operation out of several concurrent ones. The task of determining the
successful compare-and-swap operation can be viewed as a variation of tree-based combining (as in [3, 8] for example). The difference is that we do not use a tree as it would incur
Θ(log n) time overhead. Instead, our method does the combining in constant time as we
will see later.
2

In the following section, we formalize the model and the problem. In Section 5, we give
an implementation of the compare-and-swap operation using registers that support the
half-max, max-write, read and write operations. In Section 6, we prove its correctness and
show that the compare-and-swap operation runs in O(1) time. In Section 7, we argue that
the consensus numbers of the max-write and half-max primitives are both one. Finally, we
conclude and discuss some extensions in Section 8.

4

Model

A sequential object is defined by the tuple (S, O, R, T ). Here, S is the set of all possible
states of the object, O is the set of operations that can be performed on the object, R
is the set of possible return values of all the operations and T : S × O → S × R is the
transition function that specifies the next state of the object and the return value given a
state of the object and an operation applied on it.
A register is a sequential object and supports the operations read, write, half-max and
max-write. The read() operation returns the current value (state) of the register. The
write(v) operation updates the value of the register to v. The half-max(x) operation replaces the value in the first half of the register, say a, with max{x, a}. The max-write(x | y)
operation replaces the first half of the register, say a, with x and second half of the register
with y if and only if x ≥ a. The register operations are atomic, i.e., if different processes
execute them simultaneously, then they execute sequentially in some order. In general,
atomicity is implied whenever we use the word operation in the rest of the text.
An implementation of a sequential object is a collection of functions, one for each
operation defined by the object. A function specifies a sequence of instructions to be
executed when the function is executed. An instruction is an operation on a register or a
computation on local variables, i.e., variables exclusive to a process.
A process is a sequence of functions to be executed. Thus, a process defines a sequence
of instructions to be executed as determined by the individual functions in its sequence.
The processes have identifiers 1, 2, . . . , n. When a process executes a function, it is said to
call that function. A schedule is a sequence of process identifiers. Given a schedule S, an
execution E(S) is the sequence of instructions obtained by replacing each process identifier
in the schedule with the next instruction to be executed by the corresponding process.
Given an execution and a function called by a process, the start of the function call is
the point in the execution when the first register operation of the function call appears.
Similarly, the end of the function call is the point in the execution when the last register
operation of the function call appears. A function call A is said to occur before another
function call B, if the call A ends before call B starts. Thus, the function calls of an
implementation of an object O form a partial order PO (E) with respect to an execution
E. An implementation on an object O is linearizable if there is a total order TO (E) that
extends the partial order PO (E) for any given execution E so that the actual return value of

3

every functional call in the order TO (E) is same as the return value determined by applying
the specification of the object to the order TO (E). The total order TO (E) is usually defined
by associating a linearization point with each function call, which is a specific point in the
execution when the call takes effect. An implementation is wait-free if every function call
returns within a bounded number of steps of the calling process irrespective of the schedule
of the other processes.
Our goal is to develop a wait-free and linearizable implementation of the compare-andswap register. It supports read and compare-and-swap operations. The read() operation
returns the current value of the register. The compare-and-swap(a, b) operation returns
true and updates the value of the register to b if the value in the register is a. Otherwise,
it returns false and does not change the value.

5

Algorithm

Figure 1 shows the (shared) registers that are used by the algorithm. There are arrays A
and R of size n each. The ith entry of the array A consists of two fields: the field c keeps a
count of the number of compare-and-swap operations executed by the process i, the field
val is used to store or announce the second argument of the compare-and-swap operation
that the process i is executing. The ith entry of the array R consists of the fields c and ret.
The field ret is used for storing the return value of the cth compare-and-swap operation
executed by the process i. The register V stores the current value of the compare-and-swap
object in the field val along with its version number in the field seq. The fields seq, pid and
c of the register P respectively store the next version number, the process identifier of the
process that executed the latest successful compare-and-swap operation and the count of
compare-and-swap operations issued by that process. For all the registers, the individual
fields are of equal sizes except for the register P . The first half of this register stores the
field seq where as the second half stores the other two fields, pid and c.
R

A
c

c

val

ret

V seq val

P seq pid c

Figure 1: An overview of data structures used by Algorithm 1.
Algorithm 1 gives an implementation of the compare-and-swap register. To execute
the read function, a process simply reads and returns the current value of the object as
stored in the register V (Lines 20 and 21). To execute the compare-and-swap function, a
process starts by reading the current value of the object (Line 2). If the first argument of
the function is not equal to the current value, then it returns false (Lines 3 and 4). If both
4

the arguments are same as the current value, then it can simply return true as the new
value is same as the initial one (Lines 5 and 6).
Otherwise, the process competes with the other processes executing the compare-andswap function concurrently. First, the process increments its local counter (Line 7). Then,
the new value to be written by the process is announced in the respective entry of the
array A (Line 8) and the return value of the function is initialized to false by writing to
the respective entry in the array R (Line 9). The process starts competing with the other
concurrent processes by writing its identifier to the register P (Line 10). The competition is
finished by writing a version number larger than used by the competing processes (Line 11).
Algorithm 1: The compare-and-swap and the read functions. The symbol | is a
field separator. The symbol
is a variable that is not used. The variable id is the
identifier of the process executing the function. At initialization, we have c = 0 and
V = (0 | x), where x is the initial value of the compare-and-swap object.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

compare-and-swap(a, b)
(seq | val) ← V.read();
if a 6= val then
return false;

19
20
21

read()
( | val ) ← V.read();
return val ;

if a = b then
return true;
c ← c + 1;
A[id ].write(c | b);
R[id ].write(c | false);
P.max-write(seq + 1 | id | c);
P.half-max(seq + 2);
(seq | pid | cp) ← P.read();
(ca | val ) ← A[pid ].read();
if seq is even and cp = ca then
R[pid ].max-write(ca | true);
V.max-write(seq | val );
( | ret) ← R[id ].read();
return ret;

Once the winner of the competing processes is determined, the winner and the value
announced by it is read (Lines 12 and 13), the winner is informed that it won after appropriate checks (Lines 15, 14) and the current value is updated (Line 16). The value to be
returned is then read from the designated entry of array R (Line 17).
In the following section, we analyze Algorithm 1 and show that it is a linearizable and
O(1) time wait-free implementation of the compare-and-swap object.
5

6

Analysis

Let us first define some notations. We refer to a field f of a register X by X.f . The term
X.fki is the value of the field X.f just after process i executes Line k during a call. We omit
the call identifier from the notation as it will always be clear from the context. Similarly,
vki is the value of a variable v, that is local to the process i, just after it executes Line k
during a call. The term X.fe is the value of a field X.f at the end of an execution.
To prove that our implementation is linearizable, we first need to define the linearization
points. The linearization point of the compare-and-swap function executed by a process i
is given by Definition 1. There are four main cases. If the process returns from Line 4 or
Line 6, then the linearization point is the read operation in Line 2 as such an operation does
not change the value of the object (Cases 1 and 2). Otherwise, we look for the execution of
Line 16 that wrote the sequence number V.seq i2 +2 to the field V.seq for the first time. This
is the linearization point of the process i if its compare-and-swap operation was successful
as determined by the value of P.pid (Case 3a). Otherwise, the failed compare-and-swap
operations are linearized just after the successful one (Case 3b). The calls that have not
yet taken effect are linearized at the end (Case 4).
Definition 1. The compare-and-swap call by a process i is linearized as follows.
1. If V.val i2 6= ai1 , then the linearization point is the point when i executes Line 2.
2. If V.val i2 = ai1 = bi1 , then the linearization point is the point when i executes Line 2.
3. If V.val i2 = ai1 6= bi1 and V.seq e ≥ V.seq i2 + 2, then let p be the point when Line 16 is
executed by a process j so that V.seq j16 = V.seq i2 + 2 for the first time.
(a) If pid j12 = i, then the linearization point is p.
(b) If pid j12 6= i, then the linearization point is just after p.
4. If V.val i2 = ai1 6= bi1 and V.seq e < V.seq i2 + 2, then the linearization point is at the
end, after all the other linearization points.
Note that we assume in Case 3 that if V.seq e ≥ V.seq i2 + 2, then there is an execution
of Line 16 by a process j with the value V.seq j16 = V.seq i2 + 2. So, we first show in the
following lemmas that this is indeed true.
Lemma 1. The value of V.seq is always even.
Proof. We have V.seq = 0 at initialization. The modification only happens in Line 16 with
an even value.
Lemma 2. Whenever V.seq changes, it increases by 2.

6

Proof. Say that the value of the field was changed to V.seq i16 when a process i executed
Line 16. Then, the value seq i14 is even and so is the value V.seq i16 . Thus, the value
V.seq i16 was written to P.seq by a process j and that V.seq j2 = V.seq i16 − 2. As the field
V.seq is only modified by a max-write operation so it only increases. Thus, we have
V.seq ≥ V.seq i16 − 2 just before i modifies it. As V.seq is even by Lemma 1 and i modifies
it, we have V.seq = V.seq i16 − 2 before the modification. So, the value increases by 2.
Lemma 3. The linearization point as given by Definition 1 is well-defined.
Proof. The linearization point as given by Definition 1 clearly exists for all the cases except
for Case 3. Here, we only need to show that if V.seq e ≥ V.seq i2 + 2, then there exists an
execution of Line 16 by a process j so that V.seq j16 = V.seq i2 + 2. As V.seq i2 is even by
Lemma 1 and the value of V.seq only increases in steps of 2 by Lemma 2, it follows from
V.seq e ≥ V.seq i2 + 2 that V.seq i2 + 2 was written to V.seq at some point.
To show that the implementation is linearizable, we need to prove two main statements.
First, the linearization point is within the start and end of the corresponding function
call. Second, the value returned by a finished call is same as defined by the sequence of
linearization points up to the linearization point of the call. In the following two lemmas,
we show the first of these statements.
Lemma 4. If it holds that V.val i2 = ai1 6= bi1 for a compare-and-swap call by a process i,
then the value of V.seq is at least V.seq i2 + 2 at the end of the call.
Proof. We define a set of processes S = {j : V.seq j2 = V.seq i2 }. Consider the process k ∈ S
that is the first one to execute Line 14. As the first field of P.seq is always modified by a max
operation and process k writes V.seq i2 + 2 to that field, we have seq k14 = seq k12 ≥ V.seq i2 + 2.
If seq k12 > V.seq i2 + 2, then V.seq k12 ≥ V.seq i2 + 2 and we are done.
So, we only need to check the case when seq k12 = V.seq i2 + 2. As V.seq i2 is even by
Lemma 1, so is seq k14 = seq k12 . Moreover, the process pid k12 ∈ S as some process(es)
(including k) executed Line 10. As A[pid k12 ].c always increases whenever modified (Line 8),
we have ca k13 ≥ cp k12 . But, if ca k13 > cp k12 , then the process pid k12 finished even before the
process k, a contradiction. So, it holds that ca k13 = cp k12 and the process k executes Line 16.
Now, the execution of Line 16 by the process k either changes the value of V.seq or does
not. If it does, then V.seq k16 = V.seq i2 + 2 and we are done. Otherwise, someone already
changed the value of V.seq to at least V.seq i2 + 2 because of Lemma 2.
Lemma 5. The linearization point as given by Definition 1 is within the corresponding
call duration.
Proof. The statement is true for Cases 1 and 2 as the instruction corresponding to the
linearization point is executed by the process i itself.
For Case 3, we analyze the case of finished and unfinished call separately. Say that
the call is unfinished. As V.seq e ≥ V.seq i2 + 2 and V.seq i2 is the value of V.seq at the start
7

of the call, the linearization point as given by Definition 1 is after the call starts. Now,
assume that the call is finished. We know from Lemma 4 that the value of V.seq is at least
V.seq i2 + 2 when the call ends. So, the point when Line 16 writes V.seq i2 + 2 to V.seq is
within the call duration.
We know from Lemma 4 that if the call finishes, then we have V.seq e ≥ V.seq i2 + 2. So,
if V.seq e < V.seq i2 + 2, then the call is unfinished and it is fine to linearize it at the end as
done for Case 4.
Now, we need to show that the value returned by the calls is same as the value determined by the order of linearization points. We show this in the following lemmas.
Lemma 6. Assume that x = seq i12 = seq j12 for two distinct processes i and j and that x is
even. Then, it holds that pid i12 = pid j12 and cp i12 = cp j12 .
Proof. W.l.o.g. assume that the process i executes Line 12 before the process j does so.
As x = seq i12 = seq j12 by assumption, the only way in which the field P.pid can change
until the process j executes Line 12, is by a max-write operation on P with the value x as
the first field. This is not possible as x is even and the max-write on P is only executed
with odd value as the first field (Line 10). So, it holds that pid i12 = pid j12 . Similarly, we
have cp i12 = cp j12 .
Lemma 7. As long as the value of V.seq remains same, the value of V.val does not change.
Proof. Say that a process i is the first one to write a value x to V.seq. The value written
to the field V.val by the process i is val i13 . To have a different value of V.val with x as the
value of V.seq, another process j must execute Line 16 with seq j12 = x but val i13 6= val j13 .
As seq j12 = x = seq i12 , it follows from Lemma 6 that pid j12 = pid i12 and cp i12 = cp j12 . As the
condition in Line 14 is true for both the processes i and j, it then follows that ca i13 = ca j13 .
As the field A[pid j12 ].val is updated only once for a given value of A[pid j12 ].c (Line 8), it
holds that val i13 = val j13 and the claim follows.
Lemma 8. Say that seq i12 = x is even and pid i12 = j during a call by a process i, then it
holds for a call by the process j that V.seq j2 = x − 2.
Proof. As seq i12 = x, some process h modified P by executing Line 10 or Line 11 with x as
the first argument. As x is even and V.seq h2 is even by Lemma 1, the process h modified p
by executing Line 11. So, it holds that V.seq h2 = x − 2. Also, process h executed Line 10
with x − 1 as the first field. As pid i12 = j, the process j also executed Line 10 with x − 1
as the first field after the process h did so. So, it holds that V.seq j2 = x − 2.
Lemma 9. For every even value x ∈ [2, V.seq e ], there is an execution of Line 16 by a
process i so that seq i12 = x and the first such execution is the linearization point of some
call.
8

Proof. Consider an even value x ∈ [2, V.seq e ]. Then, we know from Lemma 2 that x is
written to V.seq by an execution of Line 16. Let p be the point of first execution of Line 16
by a process j so that seq j12 = x. So, it holds for the process pid j12 = h that V.seq h2 = x − 2
using Lemma 8. As point p is the first time when x is written to the field V.seq, it holds
that V.seq j16 = x. Thus, p is the linearization point of the process h by Definition 1.
Lemma 10. The value V.val is only modified at a Case 3a linearization point.
Proof. Let q be a Case 3a linearization point. Say that the value of V.seq is updated to x at
q. Let p be the first point in the execution when the value of V.seq is x−2. Using Lemma 9,
we conclude that p is either a linearization point (for x − 2 ≥ 2) or the initialization point
(for x − 2 = 0). Using Lemma 7, the value of V.val is not modified between p and q.
We want to use the above lemma in an induction argument on the linearization points
to show that the values returned by the corresponding calls are correct. First, we introduce
some notations for k ≥ 1. The term L.val k is the value of the abstract compare-and-swap
object after the k th linearization point. The terms V.seq k and V.val k , respectively, are
the values of V.seq and V.val after the k th linearization point. All these notations refer
to the respective values just after initialization for k = 0. For k ≥ 1, the term L.ret k is
the expected return value of the call corresponding to the k th linearization point. Due to
space constraints, we only give the statement of the following two lemmas without proof.
The proof is an induction on the linearization points and checks the different linearization
point cases separately.
Lemma 11. After k ≥ 0 linearization points, it holds that L.val k = V.val k except for
Case 4 linearization points. For k ≥ 1, the L.ret k values are false for Case 1, true for
Case 2, true for Case 3a and false for Case 3b.
Lemma 12. If the k th linearization point for k ≥ 1 corresponds to a finished call by a
process i, then the value returned by the call is L.ret k .
We can now state the following main theorem about Algorithm 1.
Theorem 13. Algorithm 1 is a wait-free and linearizable implementation of the compareand-swap register where both the compare-and-swap and read functions take O(1) time.
Proof. We conclude that the compare-and-swap function as given by Algorithm 1 is linearizable by using Lemma 5 and Lemma 12. The read operation is linearized at the point
of execution of Line 20. Clearly, this is within the duration of the call. To check the return
value, let LP k be the linearization point of the read operation and LP k0 be the linearization point previous to LP k . Then, we have V.val k = V.val k0 using Lemma 10. So, it holds
that V.val k = L.val k0 using Lemma 11. Moreover, both the compare-and-swap and read
functions end after executing O(1) steps and the implementation is wait-free.

9

7

Consensus Numbers

In this section, we prove that each of the max-write and the half-max primitives has consensus number one. Trivially, both operations can solve binary consensus for a single process
(itself) by just deciding on the input value. To show that these operations cannot solve
consensus for more than one process, we use the standard valency and indistinguishability
argument. We give a short proof for the reader familiar with such an argument. The
detailed proof can be found in the appendix.
We know that the initial configuration is a bivalent configuration (both 0 and 1 outputs
are possible) whereas the terminating configuration is univalent (either 0 or 1 only is a
possible output). Thus, a wait-free algorithm to solve binary consensus reaches a critical
configuration C where an operation by any process changes the configuration to a univalent
one. Say that next operation sa by process A changes the configuration to a 0-valent
configuration and the next operation sb by process B changes the configuration to a 1valent configuration. The operations sa and sb cannot be operations on different registers
as the configurations Csa sb is indistinguishable from the configuration Csb sa . It is also
not possible that one of sa or sb , say sa , is a read operation as the configurations Csa sb
and Csb are indistinguishable to process B. Both sa and sb cannot be a write operation
as the configurations Csa and Csb sa are indistinguishable to A. If both the operations are
max-write, then let sa be the operation with the greater (or equal) first argument. Then,
the configurations Csa and Csb sa are indistinguishable to A as sa overwrites sb .

8

Conclusion

The algorithm that we presented uses O(n) space to implement a single compare-and-swap
register due to the arrays A and R . If an algorithm uses m compare-and-swap registers,
then we can run m separate instances of the presented algorithm. In that case, we use
O(mn) space. But, we can save space if we observe that the algorithm uses the arrays A
and R to store the information about the latest pending call per process. As there is at
most one pending call per process even while implementing m compare-and-swap registers,
we can conceptually run m instances of the presented algorithm by using a single array A
and a single array R. In that case, the space required is O(m + n).
The half-max and max-write primitives have consensus number one each just like readwrite registers. Moreover, these primitives do not return any value and are based on the
max operation which is commutative. So, they can potentially yield a simpler and scalable
hardware implementation unlike compare-and-swap, which is known to not scale well [1].
Using our result, one can transform an algorithm that uses compare-and-swap registers into
an algorithm that uses the half-max and max-write primitives. The transformation takes
constant time per operation and works for any algorithm among processes 1, 2, . . . , n in
general, even if the algorithm not wait-free. Therefore, our result gives us an opportunity,
to rethink from scratch, the primitives to implement in a modern multi-processor.
10

References
[1] Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. Everything you always
wanted to know about synchronization but were afraid to ask. In 24th ACM Symposium on Operating System Principles (SOSP), Farminton, Pennsylvania, Nov 2013.
[2] Faith Ellen, Rati Gelashvili, Nir Shavit, and Leqi Zhu. A Complexity-Based Hierarchy
for Multiprocessor Synchronization: [Extended Abstract]. In Proceedings of the 2016
ACM Symposium on Principles of Distributed Computing (PODC), Chicago, IL, USA,
Jul 1990.
[3] Faith Ellen and Philipp Woelfel. An Optimal Implementation of Fetch-and-Increment.
In 27th International Symposium on Distributed Computing (DISC), Jerusalem, Israel,
Oct 2013.
[4] Rati Gelashvili, Idit Keidar, Alexander Spiegelman, and Roger Wattenhofer. Brief
Announcement: Towards Reduced Instruction Sets for Synchronization. In 31st International Symposium on Distributed Computing (DISC), Vienna, Austria, Oct 2017.
[5] Wojciech Golab, Vassos Hadzilacos, Danny Hendler, and Philipp Woelfel. ConstantRMR Implementations of CAS and Other Synchronization Primitives Using Read and
Write Operations. In 26th Annual ACM SIGACT-SIGOPS Symposium on Principles
of Distributed Computing (PODC), Portland, Oregon, Aug 2007.
[6] Maurice Herlihy. Wait-free Synchronization. ACM Transactions on Programming
Languages and Systems (TOPLAS), 1991.
[7] Prasad Jayanti and Srdjan Petrovic. Efficient and Practical Constructions of LL/SC
Variables. In 22nd Annual Symposium on Principles of Distributed Computing
(PODC), Boston, Massachusetts, 2003 Jul.
[8] Pankaj Khanchandani and Roger Wattenhofer. Brief Announcement: Fast Shared
Counting using O(n) Compare-and-Swap Registers. In ACM Symposium on Principles
of Distributed Computing (PODC), Washington, DC, USA, Jul 2017.
[9] Pankaj Khanchandani and Roger Wattenhofer. On the Importance of Synchronization Primitives with Low Consensus Numbers. In 19th International Conference on
Distributed Computing and Networking (ICDCN), Varanasi, India, Jan 2018.
[10] Alex Kogan and Erez Petrank. Wait-free Queues with Multiple Enqueuers and Dequeuers. In 16th ACM Symposium on Principles and Practice of Parallel Programming
(PPoPP), San Antonio, TX, USA, Feb 2011.
[11] Maged M. Michael. Practical Lock-Free and Wait-Free LL/SC/VL Implementations Using 64-Bit CAS. In 18th International Symposium on Distributed Computing
(DISC), Amsterdam, Netherlands, Oct 2004.
11

A

Proof of Lemma 11

Proof. We prove the claim by induction on k. For the base case of k = 0, the claim is true
as V.val is initialized with the initial of the compare-and-swap object. Let LP k be the k th
linearization point for k ≥ 1 and say that it corresponds to a call by a process i. We have
the following cases.
Case 1: Let LP k0 be the linearization point previous to LP k . By induction hypothesis,
it holds that L.val k0 = V.val k0 . By Lemma 10, the value of V.val does not change until LP k .
As we have a read operation at LP k , it holds that V.val k0 = V.val k . By Definition 1, we
know that V.val k 6= a1i . So, it holds that L.val k0 = V.val k0 = V.val k 6= a1i . Thus, it follows
from the specification of the compare-and-swap object that L.val k = L.val k0 = V.val k .
Moreover, we have L.ret k = false as L.val k0 = V.val k 6= a1i .
Case 2: Again, we let LP k0 to be the linearization point previous to LP k . As argued in
the previous case, it holds that V.val k0 = V.val k . By Definition 1, we know that V.val k =
a1i = b1i . So, it holds that L.val k0 = V.val k0 = V.val k = a1i . Thus, it follows from the object’s
specification that L.val k = b1i = V.val k . Further, we have L.ret k = true as L.val k0 = a1i .
Case 3a: Consider the point LP k0 when the value V.seq k − 2 was written to V.seq for
the first time. As V.seq k is even by Lemma 1, it follows from Lemma 9 that LP k0 is a
linearization point or the initialization point. Using definition of Case 3a, LP k is the first
point when the value V.seq k was written to the field V.seq. So, we have V.seq i2 = V.seq k0 .
Thus, it holds that V.val i2 = V.val k0 by Lemma 7. Therefore, V.val i2 = L.val k0 as L.val k0 =
V.val k0 by induction hypothesis. Using definition of Case 3a, it also holds that a1i = V.val i2 .
Thus, we have a1i = L.val k0 and L.val k = b1i .
Now, assume that the instruction at LP k was executed by a process j. Using definition
of Case 3a, we have i = pid j12 . As LP k is the first time when the value of V.seq is
V.seq k = V.seq i2 + 2, we conclude that the process i is not finished until LP k by using
0
Lemma 4. As seq j12 = V.seq k = V.seq i2 +2, it is true that some process i0 has V.seq i2 = V.seq i2
and that the process executed Line 10 until LP k . As i = pid j12 , the process i0 = i. Moreover,
the process i did this during the call corresponding to the linearization point LP k as it
follows from Lemma 4 that there is a unique call for any process h given a fixed value of
V.seq h2 . Thus, the process i already executed Line 8 with b1i as the value of the second
field. This field has not changed as the call by process i is not finished until LP k . So, we
have val j13 = b1i and that V.val k = b1i as well. Because a1i = L.val k0 as shown before, we
also have L.ret k = true.
Case 3b: Let LP k0 and LP k00 be the first points when the value V.seq k and V.seq k − 2 is
written to V.seq respectively (LP k0 is just before the point LP k as defined by Case 3b). Let
i and j be the processes that execute the calls corresponding to the points LP k and LP k0
respectively. By definition of Case 3b, we have V.seq i2 = V.seq k0 − 2. As process j wrote
V.seq k0 to V.seq, we have V.seq j2 = V.seq k0 − 2 as well. So, we have V.val i2 = V.val j2 using
Lemma 7. Using definition of Case 3a and Case 3b, respectively, we have a1j = V.val j2 6= b1j
and a1i = V.val i2 . So, we have a1i 6= b1j . We have b1j = L.val k0 as argued in the previous
12

case, so it holds that L.val k = L.val k0 . By induction hypothesis, we have L.val k0 = V.val k0 .
Moreover, there no operations after LP k0 and until LP k by definition of Case 3b. So,
we have V.val k0 = V.val k and thus L.val k = V.val k . Also, we have L.ret k = false as
a1i 6= b1j = L.val k0 .

B

Proof of Lemma 12

Proof. Say the k th linearization point is a Case 1 point. Using its definition, the value
returned by the corresponding call is false as the condition in Line 3 holds true. Using
Lemma 11, we have L.ret k = false as well for Case 1. Next, assume that the k th linearization point is a Case 2 point. Then, the value returned by the corresponding call is true as
the condition in Line 5 is true by definition. Using Lemma 11, we have L.ret k = true as
well for Case 2.
Now, consider that the k th linearization point is a Case 3a point. Say that the process
j executes the operation at the linearization point. As pid j12 = i by definition of Case 3a,
the process i already executed Line 10 with the first field as V.seq k − 1. So, the process
i also initialized R[i] to (cp j12 | false) in Line 9. Moreover, the process j wrote the value
(cp j12 |true) to R[i] afterwards using a max-write operation. Thus, the value of R[i].ret after
LP k is true. This field is not changed by i until it returns. And, other processes only write
true to the field. So, the call returns true which is same as the value of L.ret k given by
Lemma 11.
Next, consider that the k th linearization point is a Case 3b point. Let p be the point
when the process i initializes R[i] to a value (x | false) during the call (Line 9). Consider
a process j that tries to write true to R[i].ret after p (by executing Line 15). So, it holds
that pid j12 = i and that seq j12 is even. Now, we consider three cases depending on the
relation between seq j12 and V.seq k . First, consider that seq j12 > V.seq k . As pid j12 = i and
seq j12 is even, we have V.seq i2 = seq j12 − 2 using Lemma 8. So, we have V.seq i2 > V.seq k − 2.
This cannot happen until i finishes as V.seq i2 = V.seq k − 2 for the current call by i using
definition of Case 3b. Second, consider that seq j12 = V.seq k . Using definition of Case 3b,
there is a process h so that pid h12 6= i and seq h12 = V.seq k . As seq j12 = V.seq k by assumption,
we have pid j12 6= i using Lemma 6. This contradicts our assumption that pid j12 = i. Third,
consider that seq j12 < V.seq k . As pid j12 = i and seq j12 is even, we have V.seq i2 = seq j12 − 2
using Lemma 8. So, we have V.seq i2 < V.seq k − 2. This corresponds to a previous call by
the process i as V.seq i2 = V.seq k − 2 for the current call by i. So, it holds that ca j13 < x
and execution of Line 15 has no effect. Thus, the process i returns false for Case 3b which
matches the L.ret k value given by Lemma 11.
If the k th linearization point is a Case 4 point, then we know from Lemma 4 that the
call is unfinished and we need not consider it.

13

C

Proof of Consensus Numbers

First, we define some terms. A configuration of the system is the value of the local variables
of each process and the value of the shared registers. The initial configuration is the input
0 or 1 for each process and the initial values of the shared registers. A configuration
is called a bivalent configuration if there are two possible executions starting from the
configuration so that in one of them all the processes terminate and decide 0 and in the
other all the processes terminate and decide 1. A configuration is called 0-valent if in all
the possible executions starting from the configuration, the processes terminate and decide
0. Similarly, a configuration is called 1-valent if in all the possible executions starting
from the configuration, the processes terminate and decide 1. A configuration is called a
univalent configuration if it is either 0-valent or 1-valent. A bivalent configuration is called
critical if the next step by any process changes it to a univalent configuration. Consider
an initial configuration in which there is a process X with the input 0 and a process Y
with the input 1. This configuration is bivalent as X outputs 0 if it is made to run until
it terminates and Y outputs 1 if it is made to run until it terminates. As the terminating
configuration is univalent, a critical configuration is reached assuming that the processes
solve wait-free binary consensus.
Assume that the max-write operation can solve consensus between two processes A and
B. Then, a critical configuration C is reached. W.l.o.g., say that the next step sa by the
process A leads to a 0-valent configuration C0 and that the next step sb by the process B
leads to a 1-valent configuration C1 . In a simple notation, C0 = Csa and C1 = Csb . We
have the following cases.
1. sa and sb are operations on different registers: The configuration C0 sb is indistinguishable from the configuration C1 sa . Thus, the process B decides the same value
if it runs until termination from the configurations C0 sb and C1 sa , a contradiction.
2. sa and sb are operations on the same register and at least one of them is a read
operation: W.l.o.g., assume that sa is a read operation. Then, the configuration
C0 sb is indistinguishable to C1 with respect to B as the read operation by A only
changes its local state. Thus, the process B decides the same value if it runs until
termination from the configurations C0 sb and C1 , a contradiction.
3. sa and sb are write operations on the same register: Then, the configuration C0 sb
is indistinguishable from the configuration C1 as sb overwrites the value written by
sa . Thus, the process B will decide the same value from these configurations, a
contradiction.
4. sa and sb are max-write operations on the same register: Say that the arguments of
these operations are a | x and b | y for A and B respectively. W.l.o.g., assume that
b ≥ a. Then, the configurations C0 sb is indistinguishable from C1 as the operation

14

sb will overwrite both the fields of the register. Thus, the process B will decide the
same value from these configurations, a contradiction.
So, the critical configuration cannot be reached and the processes A and B cannot solve
consensus using the max-write primitive. For the half-max primitive, observe that it also
cannot solve consensus between the processes A and B as otherwise max-write primitive
would as well. Thus, the consensus number is one for the max-write as well as the half-max
primitive.

15

