Time Scenario Lamp Vector Money
Logical Clocks and Distributed Snapshots
Radu Nicolescu Department of Computer Science University of Auckland
28 Aug 2020
1/31
Time Scenario Lamp Vector Money
1 Time in Distributed Systems
2 Sample Scenario
3 Lamport Logical Clock
4 Vector Logical Clock
5 Global Snapshot – Count Money
2/31
Time Scenario Lamp Vector Money
Outline
1 Time in Distributed Systems
2 Sample Scenario
3 Lamport Logical Clock
4 Vector Logical Clock
5 Global Snapshot – Count Money
3/31
Time Scenario Lamp Vector Money
Philosophical Questions
• Does time exists? Is it linear? No loops?
• What is causality? Vs correlation …
• What is the meaning of happened-before? Or concurrent?
4/31
Time Scenario Lamp Vector Money
Time in distributed computing
• No global clock
• Each node has its own clock, unreliable (not totally reliable) • Never totally synchronised
• Drifts, more or less
• Can we avoid these unreliable physical clocks?
• Yes, using logical clocks, that are independent of the physical time
5/31
Time Scenario Lamp Vector Money
Time in distributed computing
• No global clock
• Each node has its own clock, unreliable (not totally reliable) • Never totally synchronised
• Drifts, more or less
• Can we avoid these unreliable physical clocks?
• Yes, using logical clocks, that are independent of the physical time
5/31
Time Scenario Lamp Vector Money
Time in distributed computing
• No global clock
• Each node has its own clock, unreliable (not totally reliable) • Never totally synchronised
• Drifts, more or less
• Can we avoid these unreliable physical clocks?
• Yes, using logical clocks, that are independent of the physical time
5/31
Time Scenario Lamp Vector Money
Time in distributed computing
• No global clock
• Each node has its own clock, unreliable (not totally reliable) • Never totally synchronised
• Drifts, more or less
• Can we avoid these unreliable physical clocks?
• Yes, using logical clocks, that are independent of the physical time
5/31
Time Scenario Lamp Vector Money
Happens-before = potential causation
• Event a happens-before event b, , , iff
1 a and b occur in the same node, and a happened before b,
according to the local clock
2 a is a send event and b is the corresponding receive event (same message, two nodes)
• here we assume that messages are sent and received one by one, but broadcasts/multicasts can be included
3 There is an event c, s.t. a ≺ c ≺ b : transitive closure
• This happens-before (a ≺ b) determines a partial order
(creates a dag)
• For us here, happens-before ≡ potential causality
a≺b
a→b
6/31
Time Scenario Lamp Vector Money
Happens-before = potential causation
• Event a happens-before event b, , , iff
1 a and b occur in the same node, and a happened before b,
according to the local clock
2 a is a send event and b is the corresponding receive event (same message, two nodes)
• here we assume that messages are sent and received one by one, but broadcasts/multicasts can be included
3 There is an event c, s.t. a ≺ c ≺ b : transitive closure
• This happens-before (a ≺ b) determines a partial order
(creates a dag)
• For us here, happens-before ≡ potential causality
a≺b
a→b
6/31
Time Scenario Lamp Vector Money
Happens-before = potential causation
• Event a happens-before event b, , , iff
1 a and b occur in the same node, and a happened before b,
according to the local clock
2 a is a send event and b is the corresponding receive event (same message, two nodes)
• here we assume that messages are sent and received one by one, but broadcasts/multicasts can be included
3 There is an event c, s.t. a ≺ c ≺ b : transitive closure
• This happens-before (a ≺ b) determines a partial order
(creates a dag)
• For us here, happens-before ≡ potential causality
a≺b
a→b
6/31
Time Scenario Lamp Vector Money
Happens-before = potential causation
• Event a happens-before event b, , , iff
1 a and b occur in the same node, and a happened before b,
according to the local clock
2 a is a send event and b is the corresponding receive event (same message, two nodes)
• here we assume that messages are sent and received one by one, but broadcasts/multicasts can be included
3 There is an event c, s.t. a ≺ c ≺ b : transitive closure
• This happens-before (a ≺ b) determines a partial order
(creates a dag)
• For us here, happens-before ≡ potential causality
a≺b
a→b
6/31
Time Scenario Lamp Vector Money
Happens-before = potential causation
• Event a happens-before event b, , , iff
1 a and b occur in the same node, and a happened before b,
according to the local clock
2 a is a send event and b is the corresponding receive event (same message, two nodes)
• here we assume that messages are sent and received one by one, but broadcasts/multicasts can be included
3 There is an event c, s.t. a ≺ c ≺ b : transitive closure
• This happens-before (a ≺ b) determines a partial order
(creates a dag)
• For us here, happens-before ≡ potential causality
a≺b
a→b
6/31
Time Scenario Lamp Vector Money
Happens-before = potential causation
(1) ab b
(2)
(3)
a
cb
a
7/31
Time Scenario Lamp Vector Money
Logical time and logical clocks
• Logical time is a mapping C from events to elements of a partially ordered set, s.t.
• Counterfactual:
• If , then a and b are called concurrent,
a ≺ b ⇒ C(a) < C(b)
C(a) ≮ C(b) ⇒ a ⊀ b
a ⊀,̸=, b
a∥b
8/31
Time Scenario Lamp Vector Money
Logical time and logical clocks
• Logical clock is a device (algorithm) that makes these mappings in a distributed network
• Must have feature: should be determined by nodes themselves
• Must have feature: unique, i.e. one-to-one (injective)
• Good feature: same times, if “essentially” same execution
• Ideal / exact match feature: – NOT all clocks!
• Factual:
• If the clock maps to a totally ordered set, then it is not “ideal”
a ≺ b ⇔ C(a) < C(b)
C(a) < C(b) ⇒ a ≺ b
9/31
Time Scenario Lamp Vector Money
Logical time and logical clocks
• Logical clock is a device (algorithm) that makes these mappings in a distributed network
• Must have feature: should be determined by nodes themselves
• Must have feature: unique, i.e. one-to-one (injective)
• Good feature: same times, if “essentially” same execution
• Ideal / exact match feature: – NOT all clocks!
• Factual:
• If the clock maps to a totally ordered set, then it is not “ideal”
a ≺ b ⇔ C(a) < C(b)
C(a) < C(b) ⇒ a ≺ b
9/31
Time Scenario Lamp Vector Money
Logical time and logical clocks
• Logical clock is a device (algorithm) that makes these mappings in a distributed network
• Must have feature: should be determined by nodes themselves
• Must have feature: unique, i.e. one-to-one (injective)
• Good feature: same times, if “essentially” same execution
• Ideal / exact match feature: – NOT all clocks!
• Factual:
• If the clock maps to a totally ordered set, then it is not “ideal”
a ≺ b ⇔ C(a) < C(b)
C(a) < C(b) ⇒ a ≺ b
9/31
Time Scenario Lamp Vector Money
Logical time and logical clocks
• Logical clock is a device (algorithm) that makes these mappings in a distributed network
• Must have feature: should be determined by nodes themselves
• Must have feature: unique, i.e. one-to-one (injective)
• Good feature: same times, if “essentially” same execution
• Ideal / exact match feature: – NOT all clocks!
• Factual:
• If the clock maps to a totally ordered set, then it is not “ideal”
a ≺ b ⇔ C(a) < C(b)
C(a) < C(b) ⇒ a ≺ b
9/31
Time Scenario Lamp Vector Money
Logical time and logical clocks
• Logical clock is a device (algorithm) that makes these mappings in a distributed network
• Must have feature: should be determined by nodes themselves
• Must have feature: unique, i.e. one-to-one (injective)
• Good feature: same times, if “essentially” same execution
• Ideal / exact match feature: – NOT all clocks!
• Factual:
• If the clock maps to a totally ordered set, then it is not “ideal”
a ≺ b ⇔ C(a) < C(b)
C(a) < C(b) ⇒ a ≺ b
9/31
Time Scenario Lamp Vector Money
Logical time and logical clocks
• Logical clock is a device (algorithm) that makes these mappings in a distributed network
• Must have feature: should be determined by nodes themselves
• Must have feature: unique, i.e. one-to-one (injective)
• Good feature: same times, if “essentially” same execution
• Ideal / exact match feature: – NOT all clocks!
• Factual:
• If the clock maps to a totally ordered set, then it is not “ideal”
a ≺ b ⇔ C(a) < C(b)
C(a) < C(b) ⇒ a ≺ b
9/31
Time Scenario Lamp Vector Money
Logical time in A#1?
• According to this definition, what is the logical time in A#1? • Message.time?
• First four components: (.time, .code, .from, .to)? • What if we drop one of these?
• Is this “ideal”? Is this total?
• Is this determined by the nodes? Or by Arcs /
• Briefly: total logical time, but Arcs is NOT a true logical clock
10/31
Time Scenario Lamp Vector Money
Logical time in A#1?
• According to this definition, what is the logical time in A#1? • Message.time?
• First four components: (.time, .code, .from, .to)? • What if we drop one of these?
• Is this “ideal”? Is this total?
• Is this determined by the nodes? Or by Arcs /
• Briefly: total logical time, but Arcs is NOT a true logical clock
10/31
Time Scenario Lamp Vector Money
Logical time in A#1?
• According to this definition, what is the logical time in A#1? • Message.time?
• First four components: (.time, .code, .from, .to)? • What if we drop one of these?
• Is this “ideal”? Is this total?
• Is this determined by the nodes? Or by Arcs /
• Briefly: total logical time, but Arcs is NOT a true logical clock
10/31
Time Scenario Lamp Vector Money
Logical time in A#1?
• According to this definition, what is the logical time in A#1? • Message.time?
• First four components: (.time, .code, .from, .to)? • What if we drop one of these?
• Is this “ideal”? Is this total?
• Is this determined by the nodes? Or by Arcs /
• Briefly: total logical time, but Arcs is NOT a true logical clock
10/31
Time Scenario Lamp Vector Money
Outline
1 Time in Distributed Systems
2 Sample Scenario
3 Lamport Logical Clock
4 Vector Logical Clock
5 Global Snapshot – Count Money
11/31
Time Scenario Lamp Vector Money
Sample Scenario – Total orders
Two compatible totals orders for essentially the same execution
P1 P2 P3
P1 P2 P3
1 2 3 4 5 6 7 8 9 10
A good logical clock should generate same logical timestamps
12/31
Time Scenario Lamp Vector Money
Outline
1 Time in Distributed Systems
2 Sample Scenario
3 Lamport Logical Clock
4 Vector Logical Clock
5 Global Snapshot – Count Money
13/31
Time Scenario Lamp Vector Money
Lamport Logical Clock – Part I
• Each processing node has its own logical clock, initialised by
• Before each internal or send event, the clock is incremented
• Each sent messages carries the sender’s clock
• After receiving a message, the receiving node updates its clock
clock = 0
clock += 1
clock = max (clock, received-clock) + 1
14/31
Time Scenario Lamp Vector Money
Lamport Logical Clock – Part I
• Each processing node has its own logical clock, initialised by
• Before each internal or send event, the clock is incremented
• Each sent messages carries the sender’s clock
• After receiving a message, the receiving node updates its clock
clock = 0
clock += 1
clock = max (clock, received-clock) + 1
14/31
Time Scenario Lamp Vector Money
Lamport Logical Clock – Part I
• Each processing node has its own logical clock, initialised by
• Before each internal or send event, the clock is incremented
• Each sent messages carries the sender’s clock
• After receiving a message, the receiving node updates its clock
clock = 0
clock += 1
clock = max (clock, received-clock) + 1
14/31
Time Scenario Lamp Vector Money
Lamport Logical Clock – Part I
Same logical timestamps for essentially the same execution
P1 P2 P3 P1 P2 P3 111
2
3 41 5
6 74 85 96
10 7
• NOT“idealorder”: P3: 4