CAP Theorem in Computing Systems: Impossibility Results and Trade-offs
I
m
p
o
s
s
i
b
i
l
i
t
y
R
e
s
u
l
t
s
:
C
A
P
,
P
R
A
M
&
F
L
P
CS 240: Computing Systems and Concurrency
Lecture 17
Marco Canini
N
e
t
w
o
r
k
p
a
r
t
i
t
i
o
n
s
d
i
v
i
d
e
s
y
s
t
e
m
s
2
N
e
t
w
o
r
k
p
a
r
t
i
t
i
o
n
s
d
i
v
i
d
e
s
y
s
t
e
m
s
3
•
Totally-ordered Multicast?
•
Bayou?
•
Dynamo?
•
Chord?
•
Paxos?
•
RAFT?
•
COPS?
H
o
w
c
a
n
w
e
h
a
n
d
l
e
p
a
r
t
i
t
i
o
n
s
?
4
H
o
w
a
b
o
u
t
t
h
i
s
s
e
t
o
f
p
a
r
t
i
t
i
o
n
s
?
5
•
Replicas appear to be a
single machine
,
but
lose
availability
during a network partition
OR
•
All replicas
remain available
during a network
partition but
do not appear to be a single machine
F
u
n
d
a
m
e
n
t
a
l
t
r
a
d
e
-
o
f
f
?
6
•
You cannot achieve all three of:
1.
Consistency
2.
Availability
3.
Partition-Tolerance
•
Partition Tolerance => Partitions Can Happen
•
Availability => All Sides of Partition Continue
•
Consistency => Replicas Act Like Single Machine
–
Specifically,
Linearizability
C
A
P
t
h
e
o
r
e
m
p
r
e
v
i
e
w
7
I
m
p
o
s
s
i
b
i
l
i
t
y
R
e
s
u
l
t
s
U
s
e
f
u
l
!
!
!
!
•
Fundamental tradeoff in design space
–
M
u
s
t
m
a
k
e
a
c
h
o
i
c
e
•
Avoids wasting effort trying to achieve the
impossible
•
Tells us the best-possible systems we can build!
8
•
From keynote lecture by Eric Brewer (2000)
–
History: Eric started Inktomi, early Internet search site based
around “commodity” clusters of computers
–
Using CAP to justify “BASE” model: Basically Available, Soft-
state services with Eventual consistency
•
Popular interpretation: 2-out-of-3
–
Consistency (Linearizability)
–
Availability
–
Partition Tolerance: Arbitrary crash/network failures
C
A
P
c
o
n
j
e
c
t
u
r
e
[
B
r
e
w
e
r
0
0
]
9
C
A
P
t
h
e
o
r
e
m
[
G
i
l
b
e
r
t
L
y
n
c
h
0
2
]
Assume to contradict that Algorithm
A
provides all of CAP
C
l
i
e
n
t
1
C
l
i
e
n
t
1
10
10
C
A
P
t
h
e
o
r
e
m
[
G
i
l
b
e
r
t
L
y
n
c
h
0
2
]
Assume to contradict that Algorithm
A
provides all of CAP
Partition Possible (from P)
C
l
i
e
n
t
1
C
l
i
e
n
t
1
11
11
C
A
P
t
h
e
o
r
e
m
[
G
i
l
b
e
r
t
L
y
n
c
h
0
2
]
Assume to contradict that Algorithm
A
provides all of CAP
Partition Possible (from P)
Write eventually returns
(from A)
C
l
i
e
n
t
1
w(x=1)
ok
C
l
i
e
n
t
1
12
12
C
A
P
t
h
e
o
r
e
m
[
G
i
l
b
e
r
t
L
y
n
c
h
0
2
]
Assume to contradict that Algorithm
A
provides all of CAP
Partition Possible (from P)
Write eventually returns
(from A)
C
l
i
e
n
t
1
w
(
x
=
1
)
o
k
C
l
i
e
n
t
1
r
(
x
)
x
=
0
Read begins after write completes
Read eventually returns (from A)
13
13
C
A
P
t
h
e
o
r
e
m
[
G
i
l
b
e
r
t
L
y
n
c
h
0
2
]
Assume to contradict that Algorithm
A
provides all of CAP
Partition Possible (from P)
Write eventually returns
(from A)
C
l
i
e
n
t
1
w
(
x
=
1
)
o
k
C
l
i
e
n
t
1
r
(
x
)
x
=
0
Read begins after write completes
Read eventually returns (from A)
Not consistent (C) => contradiction!
14
14
C
A
P
I
n
t
e
r
p
r
e
t
a
t
i
o
n
P
a
r
t
1
•
Cannot “choose” no partitions
–
2-out-of-3 interpretation doesn’t make sense
–
Instead, availability OR consistency?
•
i.e., fundamental trade-off between availability and
consistency
–
When designing system must choose one or the
other, both are not possible
15
15
C
A
P
I
n
t
e
r
p
r
e
t
a
t
i
o
n
P
a
r
t
2
•
Cannot “beat” CAP theorem
•
Can engineer systems to make partitions
extremely rare, however, and then just take the
rare hit to availability (or consistency)
16
16
M
o
r
e
t
r
a
d
e
-
o
f
f
s
L
v
s
.
C
•
Low-latency: Speak to fewer than quorum of nodes?
–
2PC:
write N, read 1
–
RAFT:
write ⌊N/2⌋ + 1, read ⌊N/2⌋ + 1
–
General:
|W| + |R| > N
•
L and C are fundamentally at odds
–
“C” = linearizability, sequential, serializability (more later)
17
17
P
A
C
E
L
C
•
If there is a partition (P):
–
How does system tradeoff A and C?
•
Else (no partition)
–
How does system tradeoff L and C?
•
Is there a useful system that switches?
–
Dynamo: PA/EL
–
“ACID” dbs: PC/EC
http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html
18
18
P
R
A
M
[
L
i
p
t
o
n
S
a
n
d
b
e
r
g
8
8
]
[
A
t
t
i
y
a
W
e
l
c
h
9
4
]
•
d
is the worst-case delay in the network over all pairs of
processes [datacenters]
•
Sequentially consistent system
•
read time + write time ≥
d
•
Fundamental tradeoff between consistency and latency!
•
(Skipping proof, see presenter notes or papers)
19
19
P
R
A
M
T
h
e
o
r
e
m
:
I
m
p
o
s
s
i
b
l
e
f
o
r
s
e
q
u
e
n
t
i
a
l
l
y
c
o
n
s
i
s
t
e
n
t
s
y
s
t
e
m
t
o
a
l
w
a
y
s
p
r
o
v
i
d
e
l
o
w
l
a
t
e
n
c
y
20
20
•
No deterministic
1-crash-robust
consensus algorithm
exists with
asynchronous
communication
“
F
L
P
”
r
e
s
u
l
t
21
21
•
Useful interpretation: no consensus algorithm can
always
reach consensus with an asynchronous
network
–
Do not believe such claims!
•
Led to lots and lots of theoretical work
–
(Consensus is possible when the network is
reasonably well-behaved)
F
L
P
i
s
t
h
e
o
r
i
g
i
n
a
l
i
m
p
o
s
s
i
b
i
l
i
t
y
r
e
s
u
l
t
f
o
r
d
i
s
t
r
i
b
u
t
e
d
s
y
s
t
e
m
s
!
22
22
•
Only 1 failure
–
Also impossible for more failures
•
For “weak” consensus (only some process needs to decide)
–
Also impossible for real consensus
•
For reliable communication
–
Also impossible for unreliable communication
•
For only two states: 0 and 1
–
Also impossible for more failures
•
For crash failures
–
Also impossible for Byzantine failures
F
L
P
’
s
w
e
a
k
a
s
s
u
m
p
t
i
o
n
s
23
23
•
Deterministic actions at each node
•
Asynchronous network communication
•
All “runs” must eventually achieve consensus
F
L
P
’
s
s
t
r
o
n
g
a
s
s
u
m
p
t
i
o
n
s
24
24
•
Initial state of system can end in decision “0” or “1”
•
Consider 5 processes, each in some initial state
[ 1,1,1,1,1 ] → 1
[ 1,1,1,1,
0
] → ?
[ 1,1,1,
0
,0 ] → ?
[ 1,1,
0
,0,0 ] → ?
[ 1,0,0,0,0 ] → 0
M
a
i
n
t
e
c
h
n
i
c
a
l
a
p
p
r
o
a
c
h
M
u
s
t
e
x
i
s
t
t
w
o
c
o
n
f
i
g
u
r
a
t
i
o
n
s
h
e
r
e
w
h
i
c
h
d
i
f
f
e
r
i
n
d
e
c
i
s
i
o
n
25
25
•
Initial state of system can end in decision “0” or “1”
•
Consider 5 processes, each in some initial state
[ 1,1,1,1,1 ] → 1
[ 1,1,1,1,0 ] → 1
[ 1,1,1,0,0 ] → 1
[ 1,1,0,0,0 ] → 0
[ 1,0,0,0,0 ] → 0
M
a
i
n
t
e
c
h
n
i
c
a
l
a
p
p
r
o
a
c
h
A
s
s
u
m
e
d
e
c
i
s
i
o
n
d
i
f
f
e
r
s
b
e
t
w
e
e
n
t
h
e
s
e
t
w
o
p
r
o
c
e
s
s
e
s
26
26
•
Goal: Consensus holds in face of 1 failure
[ 1,1,0,0,0 ] →
[ 1,1,1,0,0 ] →
M
a
i
n
t
e
c
h
n
i
c
a
l
a
p
p
r
o
a
c
h
O
n
e
o
f
t
h
e
s
e
c
o
n
f
i
g
u
r
a
t
i
o
n
s
m
u
s
t
b
e
“
b
i
-
v
a
l
e
n
t
”
(
i
.
e
.
,
u
n
d
e
c
i
d
e
d
)
:
B
o
t
h
f
u
t
u
r
e
s
p
o
s
s
i
b
l
e
1 | 0
0
27
27
•
Goal: Consensus holds in face of 1 failure
[ 1,1,0,0,0 ] →
[ 1,1,1,0,0 ] →
•
Inherent non-determinism from asynchronous network
•
Key result: All bi-valent states can remain in bi-valent
states after performing some work
M
a
i
n
t
e
c
h
n
i
c
a
l
a
p
p
r
o
a
c
h
1
0 | 1
O
n
e
o
f
t
h
e
s
e
c
o
n
f
i
g
u
r
a
t
i
o
n
s
m
u
s
t
b
e
“
b
i
-
v
a
l
e
n
t
”
(
i
.
e
.
,
u
n
d
e
c
i
d
e
d
)
:
B
o
t
h
f
u
t
u
r
e
s
p
o
s
s
i
b
l
e
28
28
1.
System thinks process
p
failed, adapts to it…
2.
But no,
p
was merely slow, not failed…
(Can’t tell the difference between slow and failed.)
3.
System think process
q
failed, adapts to it
…
4.
But no,
q
was merely slow, not failed…
5.
Repeat ad infinitum …
S
t
a
y
i
n
g
b
i
-
v
a
l
e
n
t
f
o
r
e
v
e
r
29
29
C
o
n
s
e
n
s
u
s
i
s
i
m
p
o
s
s
i
b
l
e
But, we achieve consensus all the time…
30
30
•
Deterministic actions at each node
–
Randomized algorithms can achieve consensus
•
Asynchronous network communication
–
Synchronous or even partial synchrony is sufficient
•
All “runs” must eventually achieve consensus
–
In practice, many “runs” achieve consensus quickly
–
In practice, “runs” that never achieve consensus happen
vanishingly rarely
•
Both are true with good system designs
F
L
P
’
s
s
t
r
o
n
g
a
s
s
u
m
p
t
i
o
n
s
31
31
Exploring the CAP theorem in Computing Systems and Concurrency, this presentation covers the fundamental trade-offs, handling network partitions, and the impossibility results. It delves into the implications of Consistency, Availability, and Partition-Tolerance, offering insights on designing optimal systems under these constraints.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Impossibility Results: CAP, PRAM & FLP CS 240: Computing Systems and Concurrency Lecture 17 Marco Canini
How can we handle partitions? Totally-ordered Multicast? Bayou? Dynamo? Chord? Paxos? RAFT? COPS? 4
Fundamental trade-off? Replicas appear to be a single machine, but lose availability during a network partition OR All replicas remain available during a network partition but do not appear to be a single machine 6
CAP theorem preview You cannot achieve all three of: 1. Consistency 2. Availability 3. Partition-Tolerance Partition Tolerance => Partitions Can Happen Availability => All Sides of Partition Continue Consistency => Replicas Act Like Single Machine Specifically, Linearizability 7
Impossibility Results Useful!!!! Fundamental tradeoff in design space Must make a choice Avoids wasting effort trying to achieve the impossible Tells us the best-possible systems we can build! 8
CAP conjecture[Brewer 00] From keynote lecture by Eric Brewer (2000) History: Eric started Inktomi, early Internet search site based around commodity clusters of computers Using CAP to justify BASE model: Basically Available, Soft- state services with Eventual consistency Popular interpretation: 2-out-of-3 Consistency (Linearizability) Availability Partition Tolerance: Arbitrary crash/network failures 9
CAP theorem [Gilbert Lynch 02] Assume to contradict that Algorithm A provides all of CAP Client 1 Client 1 10
CAP theorem [Gilbert Lynch 02] Assume to contradict that Algorithm A provides all of CAP Client 1 Client 1 Partition Possible (from P) 11
CAP theorem [Gilbert Lynch 02] Assume to contradict that Algorithm A provides all of CAP w(x=1) Client 1 Client 1 ok Write eventually returns (from A) Partition Possible (from P) 12
CAP theorem [Gilbert Lynch 02] Assume to contradict that Algorithm A provides all of CAP w(x=1) r(x) Client 1 Client 1 ok x=0 Read begins after write completes Read eventually returns (from A) Write eventually returns (from A) Partition Possible (from P) 13
CAP theorem [Gilbert Lynch 02] Assume to contradict that Algorithm A provides all of CAP Not consistent (C) => contradiction! w(x=1) r(x) Client 1 Client 1 ok x=0 Read begins after write completes Read eventually returns (from A) Write eventually returns (from A) Partition Possible (from P) 14
CAP Interpretation Part 1 Cannot choose no partitions 2-out-of-3 interpretation doesn t make sense Instead, availability OR consistency? i.e., fundamental trade-off between availability and consistency When designing system must choose one or the other, both are not possible 15
CAP Interpretation Part 2 Cannot beat CAP theorem Can engineer systems to make partitions extremely rare, however, and then just take the rare hit to availability (or consistency) 16
More trade-offs L vs. C Low-latency: Speak to fewer than quorum of nodes? 2PC: write N, read 1 RAFT: write N/2 + 1, read N/2 + 1 General: |W| + |R| > N L and C are fundamentally at odds C = linearizability, sequential, serializability (more later) 17
PACELC If there is a partition (P): How does system tradeoff A and C? Else (no partition) How does system tradeoff L and C? Is there a useful system that switches? Dynamo: PA/EL ACID dbs: PC/EC http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html 18
PRAM [Lipton Sandberg 88] [Attiya Welch 94] d is the worst-case delay in the network over all pairs of processes [datacenters] Sequentially consistent system read time + write time d Fundamental tradeoff between consistency and latency! (Skipping proof, see presenter notes or papers) 19
PRAM Theorem: Impossible for sequentially consistent system to always provide low latency 20
FLP result No deterministic 1-crash-robust consensus algorithm exists with asynchronous communication 21
FLP is the original impossibility result for distributed systems! Useful interpretation: no consensus algorithm can always reach consensus with an asynchronous network Do not believe such claims! Led to lots and lots of theoretical work (Consensus is possible when the network is reasonably well-behaved) 22
FLPs weak assumptions Only 1 failure Also impossible for more failures For weak consensus (only some process needs to decide) Also impossible for real consensus For reliable communication Also impossible for unreliable communication For only two states: 0 and 1 Also impossible for more failures For crash failures Also impossible for Byzantine failures 23
FLPs strong assumptions Deterministic actions at each node Asynchronous network communication All runs must eventually achieve consensus 24
Main technical approach Initial state of system can end in decision 0 or 1 Consider 5 processes, each in some initial state [ 1,1,1,1,1 ] 1 [ 1,1,1,1,0 ] ? [ 1,1,1,0,0 ] ? [ 1,1,0,0,0 ] ? [ 1,0,0,0,0 ] 0 Must exist two configurations here which differ in decision 25
Main technical approach Initial state of system can end in decision 0 or 1 Consider 5 processes, each in some initial state [ 1,1,1,1,1 ] 1 [ 1,1,1,1,0 ] 1 [ 1,1,1,0,0 ] 1 [ 1,1,0,0,0 ] 0 [ 1,0,0,0,0 ] 0 Assume decision differs between these two processes 26
Main technical approach Goal: Consensus holds in face of 1 failure One of these configurations must be bi-valent (i.e., undecided): Both futures possible [ 1,1,0,0,0 ] [ 1,1,1,0,0 ] 1 | 0 0 27
Main technical approach Goal: Consensus holds in face of 1 failure One of these configurations must be bi-valent (i.e., undecided): Both futures possible [ 1,1,0,0,0 ] [ 1,1,1,0,0 ] 1 0 | 1 Inherent non-determinism from asynchronous network Key result: All bi-valent states can remain in bi-valent states after performing some work 28
Staying bi-valent forever 1. System thinks process pfailed, adapts to it 2. But no, p was merely slow, not failed (Can t tell the difference between slow and failed.) 3. System think process q failed, adapts to it 4. But no, q was merely slow, not failed 5. Repeat ad infinitum 29
Consensus is impossible But, we achieve consensus all the time 30
FLPs strong assumptions Deterministic actions at each node Randomized algorithms can achieve consensus Asynchronous network communication Synchronous or even partial synchrony is sufficient All runs must eventually achieve consensus In practice, many runs achieve consensus quickly In practice, runs that never achieve consensus happen vanishingly rarely Both are true with good system designs 31
