17-Clocks

1 .CSC2/458 Parallel and Distributed Systems Clocks Sreepathi Pai March 22, 2018 URCS 

2 .Outline The Replica Problem Logical Clocks 

3 .Outline The Replica Problem Logical Clocks 

4 .Continuity and Contingency Planning Securities industry regulations require that brokerage firms inform their clients of their plans to address the possibility of a business disruption that potentially results from power outages, natural disasters, or other events. ... The program provides for continuation of client service within minutes in most cases. • ... • In the event that our primary data center became unavailable for any reason, we would transition to a separate back-up location, where account access would be made available. Our data centers are on separate power grids, separate flood plains and fault lines, and within different transportation networks. • ... 

5 .Replicating Data • (client1/update1) CREDIT $100 • (client2/update2) APPLY INTEREST 0.05% Update 1 Update 2 Replicated database Update 1 is Update 2 is performed before performed before update 2 update 1 

6 .Ensuring order with timestamps • All clients timestamp their messages using a single clock. • All replicas process messages in timestamp order. 

7 .Distributed clocks • All clients timestamp their messages using the clocks nearest to them. • All clocks need to synchronize with each other • What are the problems with separate clocks? 

8 .TrueTime • Assign timestamps to all database transactions • This is an interval • Use GPS clocks • derive clock signal from GPS satellites (which carry atomic clocks) • Use atomic clocks • paper refers to them as “armageddon” clocks • rubidium clocks are about $300 • Synchronization and drift are still issues • Transactions must be separated by some safe interval to be ordered • Failures (including liars) are detected and such machines are “evicted” Corbett et al., Spanner: Google’s Globally-Distributed Database, OSDI 2012. 

9 .Outline The Replica Problem Logical Clocks 

10 .Logical Clocks: Premise • Absolute time synchronization among distributed processes is not required • Processes must agree on order in which events happen • not their time 

11 .Happens-before a→b is read as event a happens-before event b • In same process, a → b if a occurs before b. • for example, in program order • If event a is “sending a message”, and event b is “receiving that message”, then a → b. • Messages cannot be received before they are sent • Messages cannot be transmitted “instantaneously” 

12 .Properties of happens-before • a → b, b → c • Is a → c? • If neither a → b nor b → a hold, then a and b are concurrent 

13 .Implementing happens-before • Assume each process has a monotonic clock • Not synchronized • Now, each event x is assigned a timestamp according to the local process • C (a) is timestamp of event a • Assume a → b (e.g. event a is sending of message, event b is receiving of message) • C (a) timestamp assigned by sender • C (b) timestamp assigned by receiver • What relationship must hold between C (a) and C (b)? 

14 .Implementing happens-before with timestamps One possible relationship that preserves properties of happens-before. If a → b, then C (a) < C (b). 

15 .Don’t we still need synchronization? P1 P2 P3 0 0 0 6 m1 8 10 12 16 20 18 24 m2 30 24 32 40 30 40 50 36 48 60 42 56 m3 70 48 64 80 54 m4 72 90 60 80 100 

16 .Lamport’s logical clocks P1 P2 P3 0 0 0 6 m1 8 10 12 16 20 18 24 m2 30 24 32 40 P2 adjusts 30 40 its clock 50 36 48 60 P1 adjusts 42 its clock 61 m3 70 48 69 80 70 m4 77 90 76 85 100 

17 .Implementing Lamport’s logical clocks Application layer Message is delivered Application sends message to application Adjust local clock Adjust local clock and timestamp message Middleware layer Middleware sends message Message is received Network layer 

18 .Implementing Lamport’s logical clocks • Each process Pi maintains local clock Ci • Before executing an event, Ci is incremented by 1 • When sending a message M, it is timestamped with Ci • When receiving a message M with timestamp T : • Cj for process Pj is adjusted to max(Cj , T ) • Cj is incremented by 1 • Message is delivered to application 

19 .Solving the Replica Problem: Total-ordered multicast • Each client multicasts a message to all replicas • Each message is timestamped according to local logical clock • Assume no loss of messages • Assume reliable ordering • Each replica places received messages in a queue • Each replica processes messages in order of timestamps • Thus, ensuring total order • QED? 

20 .Total-ordered multicast • Each client multicasts a message to all replicas • Each message is timestamped according to local logical clock • Assume no loss of messages • Assume reliable ordering • Each replica places received messages in a queue • Each replica acknowledges receipt of messages using a multicast • Each replica processes messages in order of their timestamps • Only when it has received acknowledgement for that message from all other replicas This protocol ensures all processes see the same queue. 

21 .Mutual Exclusion with Logical Clocks • Total ordered multicast produces a total order among all messages • Can be used to implement mutual exclusion • Messages: • ENTER: process multicasts that it wants to enter a critical section • ALLOW: process unicasts permission to ENTERing process • RELEASE: process multicasts that it has left a critical section 

22 .Mutual Exclusion Condition • On receiving • ENTER: placed into local queue sorted by timestamp, ALLOW sent to requesting process • ALLOW: placed into local queue sorted by timestamp • RELEASE: item at head of queue deleted • A process enters the critical section if: • its ENTER is at head of queue and • there are messages (ENTER/ALLOW) from all other processes in queue • When a process releases a critical section, it deletes all ALLOWs from its queue before multicasting RELEASE 

23 .Acknowledgements Figures from van Steen and Tanenbaum, 3rd Edition.