Synchronization Algorithms

and Concurrent Programming

Gadi Taubenfeld
Chapter 9
Consensus

Version: June 2014

Chapter 9 Synchronization Algorithms and Concurrent Programming 1
Gadi Taubenfeld © 2014
 Synchronization Algorithms
and Concurrent Programming
ISBN: 0131972596, 1st edition

A note on the use of these ppt slides:

I am making these slides freely available to all (faculty, students, readers).
They are in PowerPoint (2003) form so you can add, modify, and delete slides
and slide content to suit your needs. They obviously represent a lot of work on
my part. In return for use, I only ask the following:

q That you mention their source, after all, I would like people to use my book!
q That you note that they are adapted from (or perhaps identical to)
my slides, and note my copyright of this material.

Thanks and enjoy!

Gadi Taubenfeld
All material copyright 2014
Gadi Taubenfeld, All Rights Reserved

To get the most updated version of these slides go to:

[Link]
Chapter 9 Synchronization Algorithms and Concurrent Programming 2
Gadi Taubenfeld © 2014
 Chapter 9
Consensus

9.1 The Problem

9.2 Three Simple Consensus Algorithms
9.3 Consensus without Memory Initialization
9.4 Reaching Consensus Using a Shared Queue
9.5 Impossibility of Consensus with One Faulty
Process
9.6 The Relative Power of Synchronization Primitives
9.7 The Universality of Consensus

Chapter 9 Synchronization Algorithms and Concurrent Programming 3

Gadi Taubenfeld © 2014
 Section 9.1

Consensus

1 0 1 1 0 1 0

p1 p2 p3 p4 p5 p6 … pn

1 1 1 1 1 1 1

Each process pi has input value ini

q agreement: All non-faulty processes eventually
decides on the same value v.
q validity: v Î {in1, in2, …, inn }.

-- binary consensus ; multi-valued consensus

-- we assume crash (fail-stop) failures
Chapter 9 Synchronization Algorithms and Concurrent Programming 4
Gadi Taubenfeld © 2014
 Consensus

1 0 1 1 0 1 0

p1 p2 p3 p4 p5 p6 … pn

1 1 1 1 1 1 1

There is a trivial solution when there are no faults,

but what happens when there are faults?

Chapter 9 Synchronization Algorithms and Concurrent Programming 5

Gadi Taubenfeld © 2014
 Impossibility of Consensus with
One Faulty Process

Theorem: There is no (asynchronous) algorithm that

solves the consensus problem using atomic read/write
registers in the presence of a single faulty process.

We give a detailed proof of this important result in

Chapter 9.5 of the book.

è Same result holds also for message passing systems

What can be done?

q Strong primitives.

q Timing assumptions.
q Randomization.

Chapter 9 Synchronization Algorithms and Concurrent Programming 6

Gadi Taubenfeld © 2014
 Three Simple Consensus Algorithms
Section 9.2

Synchronization Algorithms and Concurrent Programming

Chapter 9 7
Gadi Taubenfeld © 2014
 RMW: n processes one 3-valued register
(trivial)

3-valued RMW
register

z ^

The Algorithm
q The first process to access z sets z to its input.

q All the processes adopt this value as the decision value.

èThe algorithm is wait-free (i.e., can tolerate any

number of failures)
Chapter 9 Synchronization Algorithms and Concurrent Programming 8
Gadi Taubenfeld © 2014
 RMW: Two processes three bits (trivial)

atomic atomic RMW

r/w bit r/w bit bit

r1 r2 z 0

The Algorithm
1. Each process pi uses one bit ri to announce its input.
2. Then, each process tries to set z from 0 to 1.
3. The decision value is the input of the process that
succeeds in step 2.

è The algorithm is wait-free

Chapter 9 Synchronization Algorithms and Concurrent Programming 9

Gadi Taubenfeld © 2014
 RMW: Two processes two bits (not trivial)

RMW RMW
bit bit

x 0 y 0

èThe algorithm is wait-free

Chapter 9 Synchronization Algorithms and Concurrent Programming 10
Gadi Taubenfeld © 2014
 RMW: Two processes two bits (not trivial)

RMW RMW
bit bit

x 0 y 0

Algorithm for process pi with input ini

1. If x =1 then pi decides 1 and halts, otherwise pi sets x to ini
and continues.
2. If y =0 then pi sets y to 1, decides ini and halts, otherwise pi
continues.
3. If x =0 then pi decides 0 and halts, otherwise pi decides 1-ini
.
èThe algorithm is wait-free
Chapter 9 Synchronization Algorithms and Concurrent Programming 11
Gadi Taubenfeld © 2014
 RMW: Two processes two bits (not trivial)

RMW RMW
bit bit

x 0 y 0

NO

Is the following modified version of the algorithm correct?

Algorithm for process pi with input ini
1. If x =1 then pi decides 1 and halts, otherwise pi sets x to ini
if ini =1 than pi decides 1 and halts else pi continues.
2. If y =0 then pi sets y to 1, decides ini and halts, otherwise pi
continues.
3. If x =0 then pi decides 0 and halts, otherwise pi decides 1-ini
.
Chapter 9 Synchronization Algorithms and Concurrent Programming 12
Gadi Taubenfeld © 2014
 RMW: Three processes two bits

RMW RMW
bit bit

x 0 y 0

IMPOSSIBLE!
There is NO wait-free algorithm!!!

Chapter 9 Synchronization Algorithms and Concurrent Programming 13

Gadi Taubenfeld © 2014
 Three processes many RMW bits and
atomic register

RMW
bits 0 0 0 0 0 0

atomic
read/write 0 0 0 0 0 0
registers

IMPOSSIBLE!
There is NO wait-free algorithm!!!

Theorem: There is NO consensus algorithm for n

processes that can tolerate 2 faults, for any n.

Chapter 9 Synchronization Algorithms and Concurrent Programming 14

Gadi Taubenfeld © 2014
 Two processes two atomic read/write
registers

atomic atomic
register register

x 0 y 0

IMPOSSIBLE!
There is NO wait-free algorithm!!!

Chapter 9 Synchronization Algorithms and Concurrent Programming 15

Gadi Taubenfeld © 2014
 Two processes many atomic register

atomic
read/write 0 0 0 0 0 0
registers

IMPOSSIBLE!
There is NO wait-free algorithm!!!

Theorem: There is NO consensus algorithm for n

processes that can tolerate one fault, for any n.

We will prove this very interesting theorem later.

Chapter 9 Synchronization Algorithms and Concurrent Programming 16

Gadi Taubenfeld © 2014
 RMW: many processes, four bits,
at most one fault

RMW
bits 0 0 0 0
x y decision finish

Chapter 9 Synchronization Algorithms and Concurrent Programming 17

Gadi Taubenfeld © 2014
 RMW: n processes, four bits,
at most one fault

RMW
bits 0 0 0 0
x y decision finish

The Algorithm
1. Process 1 and process 2 execute the algorithm for two
processes using x and y.
2. Then, they write the decision value into the decision bit
and set finish to 1.
3. Each other process busy waits until finish=1, and then
decides on the value of the decision bit.

Chapter 9 Synchronization Algorithms and Concurrent Programming 18

Gadi Taubenfeld © 2014
 RMW: n processes, four bits,
at most one fault

RMW
bits 0 0 0 0
x y decision finish

Is it important that all the four bits are initially 0 ?

No, the initial value of the decision bit is immaterial.

Chapter 9 Synchronization Algorithms and Concurrent Programming 19

Gadi Taubenfeld © 2014
 Important Conclusion

RMW Theorem: There is a consensus algorithm for n

bits processes that can tolerate one fault, for any n.

read/write
registers
Theorem: There is NO consensus algorithm for n
processes that can tolerate one fault, for any n.

It is not possible to implement a single RMW bit for

two processes or more, from atomic read/write
registers, that can tolerate one fault.

Chapter 9 Synchronization Algorithms and Concurrent Programming 20

Gadi Taubenfeld © 2014
 Question
Crash-safe semaphores

Why is it not possible to implement a semaphore S for

three processes or more, from RMW bits (or test-and-
set bits) and atomic read/write registers (no kernel
calls), which supports the usual up(S) and down(S)
operations, and in addition, it is possible to infer which
process holds the semaphore S ?

(Semaphores are defined in Section 4.6, page 176.)

Chapter 9 Synchronization Algorithms and Concurrent Programming 21

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization
Section 9.3

Synchronization Algorithms and Concurrent Programming

Chapter 9
Gadi Taubenfeld © 2014
 Consensus without Memory Initialization

RMW register Q: How big?

(not bit) ?
A: 3n values.

Solve the consensus problem in the following model:

q There are n processes that communicate via a single
“large enough” RMW register.
q The initial value of the register is not a priori known.
q As always, processes are asynchronous.
q Processes may crash.
We assume that at most n/2 -
1 processes may crash.
How
With would we
a known do it
initial in a
value, Impossible if n/2
fault-free
it can be donemodel?
with a 3- processes may crash!
valued register.

Chapter 9 Synchronization Algorithms and Concurrent Programming 23

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization
A single RMW register with 3n values

bit é1.5n -1ù B = {0,1}

? ? C = {0, é1.5n -2ù

b c

0 0

circle circle
b=0 b=1

n én/2ù n én/2ù

Chapter 9 Synchronization Algorithms and Concurrent Programming 24

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization
Example: n = 10

n = 10
0 4
B = {0,1}
b c C = {0,…,13}

0 0

circle circle
b=0 b=1

n én/2ù n én/2ù
10 5 10 5

Chapter 9 Synchronization Algorithms and Concurrent Programming 25

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization

0 0
n =10
circle circle
b=0 b=1
0 4
5
11
n én/2ù n én/2ù
b c
10 5 10 5

The Algorithm:
q Each process reads the value of the shared register,
0 4
stores it, and increments c by one (modulo |C|).
q A process becomes the master if it learns (by
inspecting c) that more than half of the processes
have waked up and the value of b has not changed.

Chapter 9 Synchronization Algorithms and Concurrent Programming 26

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization

0 0 Example:
n =10
v=0
0-interval 0-interval Example:
0 v = 11
1
b c
10 1-interval 5 10 1-interval 5

The master:
q The master decides on its own input value, say v ;
one
q if v = 0 then c ç 0 else c ç én/2ù ; atomic
action
q if b = 0 then b ç 1 else b ç 0;

Chapter 9 Synchronization Algorithms and Concurrent Programming 27

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization

0 0
n =10
0-interval 0-interval
1 5

b c
10 1-interval 5 10 1-interval 5

The master:
q continues forever setting c to the beginning of the
interval corresponding to the decision.
(i.e., if v = 0 then c ç 0 else c ç én/2ù )

Chapter 9 Synchronization Algorithms and Concurrent Programming 28

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization

0 0
n =10
0-interval 0-interval
1 5

b c
10 1-interval 5 10 1-interval 5

Every other process:

q find outs that a decision has been made:
Ø b changed value, or
Ø c has been incremented by more than n (modulo |C|) ;
q makes a decision according to the interval in which c lies ;

Chapter 9 Synchronization Algorithms and Concurrent Programming 29

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization

0 0
n =10
0-interval 0-interval
1 5

b c
10 1-interval 5 10 1-interval 5

Every process:
q after making its decision, continues forever
setting c to the beginning of the interval
corresponding to its decision.

Chapter 9 Synchronization Algorithms and Concurrent Programming 30

Gadi Taubenfeld © 2014
 Consensus without Memory Initialization

Comments:
q There is a fault-free solution that uses only 5
values. (Based on the See-Saw Barrier, page 215.)
q The known lower bound (when there are faults) is
Ω(n0.63) values.

Chapter 9 Synchronization Algorithms and Concurrent Programming 31

Gadi Taubenfeld © 2014
Reaching Consensus using a Shared Queue
Section 9.4

Synchronization Algorithms and Concurrent Programming

Chapter 9
Gadi Taubenfeld © 2014
 Reaching Consensus using a Shared Queue

Requirements:
q Solution must be wait-free.
q Can use many queues & atomic registers

Observations:
q With a peek operation – trivial for many processes.
q Three processes – Impossible! (without peek)
q Two processes with initialized queue – trivial (without peek)
q Two processes with empty queue – not trivial (without peek)

Chapter 9 Synchronization Algorithms and Concurrent Programming 33

Gadi Taubenfeld © 2014
 Reaching Consensus using a Shared Queue
Program for process pi with input ini

if ini = 0 then Queue,

enqueue(Q,0) initially empty
if R=0 then decide(0)
else Q
if dequeue(Q) = empty
then decide(0) Atomic bit
else decide (1) fi
fi R 0
else
R:=1
if dequeue(Q) = empty
then decide(1)
else decide (0) fi
fi

Chapter 9 Synchronization Algorithms and Concurrent Programming 34

Gadi Taubenfeld © 2014
 Impossibility of Consensus with One Faulty
Process
Section 9.5

Synchronization Algorithms and Concurrent Programming

Chapter 9
Gadi Taubenfeld © 2014
 Section 9.5

Impossibility of Consensus with

One Faulty Process

Theorem: There is no (asynchronous) algorithm that

solves the consensus problem using atomic read/write
registers in the presence of a single faulty process.

èSame result holds also for message passing systems.

Why?

Chapter 9 Synchronization Algorithms and Concurrent Programming 36

Gadi Taubenfeld © 2014
 Section 9.5

Impossibility of Consensus with

One Faulty Process

Notions: run
q run, empty run,
state
event

Chapter 9 Synchronization Algorithms and Concurrent Programming 37

Gadi Taubenfeld © 2014
 bivalent & univalent

bivalent
step by p step by q

time
bivalent bivalent

bivalent 0-valent bivalent 1-valent

0 1 0 0 0 1 1 1

final decision values

Chapter 9 Synchronization Algorithms and Concurrent Programming 38

Gadi Taubenfeld © 2014
 Lemma 1
(simple)

Any consensus algorithm that can tolerate one crash failure

has a bivalent empty run (i.e., bivalent initial state).

bivalent

0 1

Chapter 9 Synchronization Algorithms and Concurrent Programming 39

Gadi Taubenfeld © 2014
 Lemma 1
Proof

Any consensus algorithm that can tolerate one crash failure

has a bivalent empty run.

0000 0001 0011 0111 1111

0 0 0 1 1 1

Chapter 9 Synchronization Algorithms and Concurrent Programming 40

Gadi Taubenfeld © 2014
 Proof of the theorem

Assume to the contrary that CONS is a consensus algorithm

that can tolerate one crash failure ...
other processes may
bivalent take steps, but p1 must
step by p1 take at least one step

step by p2
Since CONS is correct,
this run can not be
extended forever.
step by pn

step by p1 x
step by p2
è for some process p,
for every extension y of
step by pn x the run yp is univalent.

Chapter 9 Synchronization Algorithms and Concurrent Programming 41

Gadi Taubenfeld © 2014
 Proof of the theorem

for every extension y of

x the run yp is univalent

single step x
by p
no steps by p

the shortest
extension of x
which is

Chapter 9 Synchronization Algorithms and Concurrent Programming 42

Gadi Taubenfeld © 2014
 Proof of the theorem

single step x
by p
no steps by p

option 1:
single step
single step by p
by p

Chapter 9 Synchronization Algorithms and Concurrent Programming 43

Gadi Taubenfeld © 2014
 Proof of the theorem

single step x
by p
no steps by p

option 2:
not a step
by p

single step
by p

Chapter 9 Synchronization Algorithms and Concurrent Programming 44

Gadi Taubenfeld © 2014
 Proof of the theorem
Four cases
So, in both option 1 and option 2 p q
we get the following picture
read read
write read
single step x read write
by p
write write
no steps by p

p q

Chapter 9 Synchronization Algorithms and Concurrent Programming 45

Gadi Taubenfeld © 2014
 Proof of the theorem
Four cases
p q
read read
write read
read write
write write

p q

Chapter 9 Synchronization Algorithms and Concurrent Programming 46

Gadi Taubenfeld © 2014
 Proof of the theorem
Four cases
p q
read read
p q
write read
p read write
write write

q does not
take steps

decide 0

A contradiction

Chapter 9 Synchronization Algorithms and Concurrent Programming 47

Gadi Taubenfeld © 2014
 Proof of the theorem
Four cases
p q
read read
p q
write read
read write
q p
write write

p does not
take steps

decide 0

A contradiction

Chapter 9 Synchronization Algorithms and Concurrent Programming 48

Gadi Taubenfeld © 2014
 Proof of the theorem
Four cases
p q
read read
p q
write read
read write
q p
write write

All processes • different registers

take steps
• same register

decide 0

A contradiction

Chapter 9 Synchronization Algorithms and Concurrent Programming 49

Gadi Taubenfeld © 2014
 Proof of the theorem
Four cases
p q
read read
p q
write read
p read write
write write

q does not
take steps

• different registers
• same register
decide 0

A contradiction

Chapter 9 Synchronization Algorithms and Concurrent Programming 50

Gadi Taubenfeld © 2014
 Proof of the theorem

QED

Chapter 9 Synchronization Algorithms and Concurrent Programming 51

Gadi Taubenfeld © 2014
 The Relative Power of Synchronization
Primitives
Section 9.6

Synchronization Algorithms and Concurrent Programming

Chapter 9
Gadi Taubenfeld © 2014
The Relative Power of Synchronization Primitives

Definition: The consensus number of an object of type o,

denoted CN(o), is the largest n for which it is possible to
solve consensus for n processes using any number of objects
of type o and any number of atomic registers. If no largest n
exists, the consensus number of o is infinite.

Examples:
• CN(atomic-register) = 1
• CN(read-modify-write bit) = 2
• CN(queue) = 2
• CN(3-valued read-modify-write register) = ¥
• CN(compare-and-swap) = ¥

Chapter 9 Synchronization Algorithms and Concurrent Programming 53

Gadi Taubenfeld © 2014
 Section 9.6

The Relative Power of Synchronization Primitives

Consensus object
Number
1 atomic-register, atomic-snapshot, safem, regularm
2 test-and-set, fetch-and-increment, fetch-and-add,
swap, queue, stack, read-modify-write bit,
fetch-and-incrementm, fetch-and-addm
Q(Öm) swapm
2m-2 m-register assignment, atomic-registerm (m>1)
¥ compare-and-swap, LL/SC, sticky-bit, queue2,
3-valued read-modify-write, augmented-queue

Om is an object in which a process is allowed to atomically

access m objects of type O

Chapter 9 Synchronization Algorithms and Concurrent Programming 54

Gadi Taubenfeld © 2014
 Section 9.6

The Relative Power of Synchronization Primitives

Consensus object
Number
1 atomic-register, atomic-snapshot, safem, regularm
2 test-and-set, fetch-and-increment, fetch-and-add,
swap, queue, stack, read-modify-write bit,
fetch-and-incrementm, fetch-and-addm
Q(Öm) swapm
2m-2 m-register assignment, atomic-registerm (m>1)
¥ compare-and-swap, LL/SC, sticky-bit, queue2,
3-valued read-modify-write, augmented-queue

Theorem: Let o1 and o2 be two objects such that CN(o1) < CN(o2).
Then, in a system with CN(o2) processes,
q There is no wait-free implementation of an object of type o2
from objects of type o1 and atomic registers;
q There is a wait-free implementation of an object of type o1
from objects of type o2 and atomic registers.
Chapter 9 Synchronization Algorithms and Concurrent Programming 55
Gadi Taubenfeld © 2014
 Section 9.6

The Relative Power of Synchronization Primitives

Consensus object
Number
1 atomic-register, atomic-snapshot, safem, regularm
2 test-and-set, fetch-and-increment, fetch-and-add,
swap, queue, stack, read-modify-write bit,
fetch-and-incrementm, fetch-and-addm
Q(Öm) swapm
2m-2 m-register assignment, atomic-registerm (m>1)
¥ compare-and-swap, LL/SC, sticky-bit, queue2,
3-valued read-modify-write, augmented-queue

Theorem: Let o1 and o2 be two objects with consensus number n.

Then, using any number of additional atomic registers,
q The objects o1 and o2 can wait-free implement each other
when the number of processes is less than or equal to n;
q The objects o1 and o2 do not necessarily wait-free implement
each other when the number of processes is more than n.
Chapter 9 Synchronization Algorithms and Concurrent Programming 56
Gadi Taubenfeld © 2014
 Open Question
Consensus object
Number
1 atomic-register
2 test-and-set, fetch-and-increment, fetch-and-add,
swap, queue, stack, read-modify-write bit

Q(Öm)
2m-2
¥

Chapter 9 Synchronization Algorithms and Concurrent Programming 57

Gadi Taubenfeld © 2014
 The Universality of Consensus
Section 9.7

Synchronization Algorithms and Concurrent Programming

Chapter 9
Gadi Taubenfeld © 2014
 Section 9.7

Universality

Definition: An object o is universal for n processes if

Ø any object that has sequential specification has
Ø wait-free
Ø linearizable implementation
Ø using atomic registers and objects of type o
Ø in a system with n processes.

Chapter 9 Synchronization Algorithms and Concurrent Programming 59

Gadi Taubenfeld © 2014
 Section 9.7

The Universality of Consensus

Definition: An object o is universal for n processes if

Ø any object that has sequential specification has
Ø wait-free
Ø linearizable implementation
Ø using atomic registers and objects of type o
Ø in a system with n processes.

Theorem: A consensus object for n processes is universal

in a system with n processes, for any positive n.

Chapter 9 Synchronization Algorithms and Concurrent Programming 60

Gadi Taubenfeld © 2014
 Section 9.6

Consensus Numbers & Universality

Consensus object
Number
1 atomic-register, atomic-snapshot, consensus(1)
2 test-and-set, fetch-and-increment, fetch-and-add,
swap, queue, stack, consensus(2)
fetch-and-incrementm, fetch-and-addm
Q(Öm) swapm consensus(Öm)
2m-2 m-register assignment, consensus(2m-2)
¥ compare-and-swap, LL/SC, sticky-bit, queue2,
3-valued read-modify-write, consensus(¥)

Theorem: A consensus object for n processes is universal

in a system with n processes, for any positive n.

Chapter 9 Synchronization Algorithms and Concurrent Programming 61

Gadi Taubenfeld © 2014
 Section 9.7

The Universality of Consensus: Proof

A detailed proof appears in Section 9.7

Chapter 9 Synchronization Algorithms and Concurrent Programming 62

Gadi Taubenfeld © 2014