程序代写代做代考 algorithm graph C distributed system clock Time Scenario Lamp Vector Money

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
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
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 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 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 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