Outline Theoretical Foundations Fundamental limitations of distributed systems Logical clocks 01 13 19 COP5611 1 Lamport s Logical Clocks review Definitions Happened before relation Happened before relation captures the causal dependencies between events It is defined as follows a b if a and b are events in the same process and a occurred before b a b if a is the event of sending a message m in a process and b is the event of receipt of the same message m by another process If a b and b c then a c i e is transitive 01 13 19 COP5611 2 Lamport s Logical Clocks review Definitions continued Causally related events Event a causally affects event b if a b Concurrent events Two distinct events a and b are said to be concurrent denoted by a b if a b and b a For any two events either a b b a or a b 01 13 19 COP5611 3 Lamport s Logical Clocks review Logical clocks There is a clock at each process Pi in the system Which is a function that assigns a number to any event a called the timestamp of event a at Pi The numbers assigned by the system of the clocks have no relation to physical time The logical clocks take monotonically increasing values and can be implemented as counters 01 13 19 COP5611 4 Lamport s Logical Clocks cont Conditions satisfied by the system of clocks For any two events if a b then C a C b C1 For any two events a and b in a process Pi if a occurs before b then Ci a Ci b C2 If a is the event of sending a message m in process Pi and b is the event of receiving the same message m at process Pj then Ci a Cj b 01 13 19 COP5611 5 Lamport s Logical Clocks cont Implementation rules IR1 Clock Ci is incremented between any two successive events in process Pi Ci Ci d d 0 IR2 If event a is the sending of message m by process Pi then message m is assigned a timestamp tm Ci a On receiving the same message m by process Pj Cj is set to Cj max Cj tm d 01 13 19 COP5611 6 An Example 01 13 19 COP5611 7 Total Ordering Using Lamport s Clocks If a is any event at process Pi and b is any event at process Pj then a b if and only if either Ci a C j b or Ci a C j b and Pi Pj Where is any arbitrary relation that totally orders the processes to break ties 01 13 19 COP5611 8 Example Totally Ordered Multicasting 01 13 19 COP5611 9 A Limitation of Lamport s Clocks In Lamport s system of logical clocks If a b then C a C b The reverse if not necessarily true if the events have occurred on different processes 01 13 19 COP5611 10 A Limitation of Lamport s Clocks 01 13 19 COP5611 11 Vector Clocks Implementation rules IR1 Clock Ci is incremented between any two successive events in process Pi Ci i Ci i d d 0 IR2 If event a is the sending of message m by process Pi then message m is assigned a timestamp tm Ci a On receiving the same message m by process Pj Cj is set to Cj k max Cj k tm k 01 13 19 COP5611 12 Vector Clocks cont 01 13 19 COP5611 13 Vector Clocks cont 01 13 19 COP5611 14 Vector Clocks cont Assertion At any instant i j Ci i C j i Events a and b are casually related if t a tb or tb ta Otherwise these events are concurrent In a system of vector clocks a a b iff t t 01 13 19 COP5611 b 15 Causal Ordering of Messages The causal ordering of messages try to maintain the same causal relationship that holds among message send events with the corresponding message receive events In other words if Send M1 Send M2 then Receive M1 Receive M2 This is different from causal ordering of events 01 13 19 COP5611 16 Causal Ordering of Messages cont 01 13 19 COP5611 17 Causal Ordering of Messages cont The basic idea It is very simple Deliver a message only when no causality constraints are violated Otherwise the message is not delivered immediately but is buffered until all the preceding messages are delivered 01 13 19 COP5611 18 Birman Schiper Stephenson Protocol 01 13 19 COP5611 19 Schiper Eggli Sando Protocol 01 13 19 COP5611 20 Schiper Eggli Sando Protocol cont 01 13 19 COP5611 21 Schiper Eggli Sando Protocol cont 01 13 19 COP5611 22
View Full Document
Unlocking...