11Time, Clocks, and theOrdering of Events ina Distributed SystemBy: Leslie LamportPresented by: Konstantin Berlinhttp://www.cs.umd.edu/~kberlin/cmsc714/cmsc714pres.ppt2Introduction How do you assign order to events happing in a distributed system? No central clock. Theoretically impossible to fully synchronize clocks. Decentralized3Outline Introduction The Partial Ordering Logical Clocks Total Ordering of Events Physical Clocks Applications Conclusion4The Partial Ordering Definition: “happened before”, denoted as →, 1) If a and b are events in the same process, and a comes before b, then a→b. 2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a→b. 3) If a→band b→c then a→c. Two distinct events a and b are said to be concurrent if a!→band b!→a.4) a!→a for any event a.•p1→p3, q1→q7•p1→q2, q1→r4•p1→q4, p1→r4, p3 concurrentq35Logical Clocks Define clock Ci<a> on processor Pias function that assigns number to event “a”. Ci: a -> N0 Define C<a>= Ci<a> if a is event on Pi. Clock Condition: For all a,b: if a→b, then C<a> < C<b>6Logical Clocks: Satisfying clock condition IR1. Each process Piincrements Cibetween any two successive events. IR2. (a) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm= Ci(a). (b) Upon receiving a message m, process Pisets Cigreater than or equal to its present value and greater than Tm.27Total Ordering of Events Using logical clocks it is simple to produce a total ordering of events (⇒) a⇒b if and only if either i. Ci<a> < Cj<b>ii. Ci(a) = Cj(b) and Pi< Pj. a→b implies a⇒b8Outline Background The Partial Ordering Logical Clocks Total Ordering of Events Physical Clocks Applications Conclusion9Strong Clock Condition What happens when some communication is out of band? Remember IR2 (b) condition Upon receiving a message m, process Pisets Cigreater than or equal to its present value and greater than Tm. Because message was send out of band, it is possible that a→b, but C<a> > C<b>. Strong Clock Condition Let a->b, as a happening before b. For any events a, b in L, if a->b then C<a> <C<b>.10Physical Clock Introduce a physical clock Accurate There exists a constant κ << 1, such that for all i: |dCi(t)/dt - 1| < κ Synchronized For all i, j: |Ci(t) -Cj(t)| < ε Avoid anomalous behavior For any i, j, t: Ci(t+µ) –Cj(t) > 0. Where µis the transmission speed. ε/(1- κ)≤µmust hold11Physical Clock: Synchronization When Pisends a message m at physical time t to Pj, m contains a timestamp Tm= C/(t). Upon receiving a message m at time t', process Pjsets Cj(t')=max(Cj(t' - 0), Tm+ min delay) Theorem states that given the bounds on maximum number of hops and if messages are send frequently enough, synchronization condition For all i, j: |Ci(t) -Cj(t)| < εholds12Applications Granting exclusive right to a resource Use logical clocks to assign ordering to requests (done individually at each process) Move on to next task as soon as got confirmation of a release. Updates in Peer-to-Peer network313Conclusion
View Full Document
Unlocking...