Conflict Resolution
with guns
Controversy
What is distributed?
time & space
Time
Space
Coordination
Failure
Master-Slave
Failure?
Leader-Election
Dead?
or just not responding?
CAP Theorem
Consistency, Availability, Partition tolerance
Can we do better?
PAXOS! RAFT!
Complexity
Challenge
Consistency
Challenge
Centralization
Conflict Resolution
with guns
In Space!
:(
or on the metro
Cause we Can’t Beat Light
5
2
-3
a quantifiable difference
Where “Quantum” Mechanics Comes From
The Universe
is not Strongly Consistent
Who Wins?
Hello: “Mars”
Hello: “Earth”
Divergence
Hello: “Mars”
Hello: “Earth”
Terrible Timestamps
I’m from the future `yo!
Villainous Vectors
I catch your drift, but you lost me.
Alice says “Hello World” at 1
Alice says “Hello Mars” at 2
Bob says “Hello Jupiter” at 5
Alice says “Hello Pluto” at 6
I’m Carl and
I want to be
your friend!
c
No.
Can we do better?
or back to strong consistency?
Boundary Function
Operating State
Historical State
Deferred State
?
?
state 8
state 4
Hello: “Mars”
state 9
state 8
state 4
Hello: “Mars”
state 9
state 8
state 4
✖ Process Later
Hello: “Sun”
state 3
state 8
state 4
Hello: “Sun”
state 3
state 8
state 4
✖ Record & Discard
Hello: “Venus”
state 5
state 8
state 4
Hello: “Venus”
state 5
state 8
state 4
✔ Process
state 8
state 5
state 9
state 5
state 9
state 5
Hello: “Earth”
state 9
✔ Process
state 9
state 9
Hello: “Mars”
state 9
state 9
state 12
State 9 === State 9
Conflict!
?
value === value
Earth vs Mars
current value compared to incoming value
Naïve
lexical alphanumeric sort
Hello: “Mars”
state 9
state 12
Hello: “Earth”
state 9
Convergence
Hello: “Mars”
Hello: “Mars”
Eventually
What Could Go Wrong?
function HAM(machineState, incomingState, currentState, incomingValue, currentValue){
if(machineState < incomingState){
return {defer: true};
}
if(incomingState < currentState){
return {historical: true};
}
if(currentState < incomingState){
return {converge: true, incoming: true};
}
if(incomingState === currentState){
if(Lexical(incomingValue) === Lexical(currentValue)){
return {state: true};
}
if(Lexical(incomingValue) < Lexical(currentValue)){
return {converge: true, current: true};
}
if(Lexical(currentValue) < Lexical(incomingValue)){
return {converge: true, incoming: true};
}
}
return {err: "Invalid recursion"};
}
NTP
Causality
Linked Lists & Directed Acyclic Graphs
X + Y - Z * A / B ^ C
Conflict-free Replicated Data Types
Math → Banking
Vulnerable to the Double Spending Problem
Blockchain Ledger
Proof of Work
Batteries Not Included
Extensible
Your Business
Distributed Matters
Decentralized Matters
Math Matters
Science Matters
CRDTs, DAGs, Blockchains
c
Hey!
Will you
be my
friend?
People Matter
mark@gunDB.io