TIME, CLOCKS AND THE ORDERING OF EVENTS IN A DISTRIBUTED SYSTEMTHE PAPERORDERING EVENTSRelation “has happened before” (I)Example (I)Example (II)Relation “has happened before” (II)Logical clocksImplementation rulesDefining a total orderAnomalous behaviorsExampleStrong clock conditionPhysical clock conditionsSlide 15ObservationsSlide 17TIME, CLOCKS AND THE ORDERING OF EVENTS IN A DISTRIBUTED SYSTEML. LamportComputer Science LaboratorySRI InternationalTHE PAPER•Addresses the problem of clock drift in distributed systems•Identify main function of computer clocksto order events•Indicates which conditions clocks must satisfy to fulfill their role•Introduces logical clocksORDERING EVENTS•Event ordering linked with concept of causality:–Saying that event a happened before event b is same as saying that event a could have affected the outcome of event b–If events a and b occur on processes that do not exchange any data, their exact ordering is not importantRelation “has happened before” (I)•Smallest relation satisfying the three conditions:–If a and b are events in the same process and a comes before b, then a  b–If a is the sending of a message by a process and b its receipt by another process then a  b–If a  b and b  c then a  cExample (I)Process iProcess kProcess jXXXXXXXXXXacbdeExample (II)•From first condition–a  d–c  e•From second condition–a  c–b e•From third condition–a  eRelation “has happened before” (II)•We cannot always order events: relation “has happened” before is only a preorder•If a did not happen before b, it cannot causally affect bLogical clocks•Verify the clock condition:if a  b then C<a> < C<b>and the two subconditions:–if a and b are events in process Pi and a comes before b, then Ci<a> < Ci<b>–if a is the sending of a message by Pi and b its receipt by Pj then Ci<a> < Cj<b>Implementation rules •Each process Pi increments its clock Ci between two consecutive events,•If a is the sending of a message m by Pi then m includes a timestamp Tm = Ci<a>when Pj receives m, it sets its clock to a value greater than or equal to its present value and greater than TmDefining a total order•We can define a total ordering on the set of all system eventsa  b if either Ci<a> < Cj<b> or Ci<a> = Cj<b> and Pi < Pj•This ordering is not uniqueAnomalous behaviors•Logical clocks have anomalous behaviors in the presence of outside interactions–Carrying a flash drive from one machine to another–Dictating file changes over the phone•Must use physical clocksExample Process iProcess kProcess jXXXXXXXXXXacbdeoutside interactionStrong clock condition•Let S be set of all systems events plus the relevant external events•For all events a, b in S,if a  b then C(a) < C(b)Physical clock conditions•There is a constant  << 1 such that for all i:| d Ci(t) / dt - 1 | < The clock is neither too fast nor too slow•There is a constant  such that for all i, j:| Ci(t) - Cj(t) | < The clocks are more or less synchronizedImplementation rules •If Pi does not receive a message at time t then Ci(t) is differentiable and dCi(t)/dt > 0•If Pi sends message m at time t then m includes a timestamp Tm = Ci(t)When Pj receives m at time t’,it sets Cj(t’) to maximum of Cj(t’-0) and Tm+m,where m is the minimum transmission delayObservations•Like logical clocks, physical clocks cannot be rolled back•Required accuracy of a given physical clock depends on the minimum transmission delay of outside interactions–If it takes 20 minutes to carry a flash drive between two machines, their clocks can beoff by up to 20 minutesExample Process iProcess jXXXXXX11:30 amdOK11:15 amXX11:30