Chapter 3: Logical Time

1 Chapter 3: Logical TimeAjay Kshemkalyani and Mukesh SinghalDistributed Computing: Principles, Algorithms, and SystemsCambridge University PressA. Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 20081 / 67 Distributed Computing: Principles, Algorithms, and SystemsIntroductionThe concept of causality between events is fundamental to the design andanalysis of parallel and distributed computing and operating causality is tracked using physical distributed systems, it is not possible to have a global physical asynchronous distributed computations make progress inspurts, thelogical time is sufficient to capture the fundamental monotonicity propertyassociated with causality in distributed Kshemkalyani and M.

2 Singhal (Distributed Computing) Logical TimeCUP 20082 / 67 Distributed Computing: Principles, Algorithms, and SystemsIntroductionThis Chapter discusses three ways to implement Logical time- scalar time,vector time, and matrix among events in a distributed system is a powerfulconcept inreasoning, analyzing, and drawing inferences about a knowledge of the causal precedence relation among the events ofprocesses helps solve a variety of problems in distributed systems, such asdistributed algorithms design, tracking of dependent events, knowledge aboutthe progress of a computation, and concurrency Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 20083 / 67 Distributed Computing: Principles, Algorithms, and SystemsA Framework for a System of Logical ClocksDefinitionA system of Logical clocks consists of a time domainTand a Logical ofTform a partially ordered set over a relation<.

3 Relation<is called thehappened beforeorcausal precedence. Intuitively,this relation is analogous to theearlier thanrelation provided by the Logical clockCis a function that maps an eventein a distributedsystem to an element in the time domainT, denoted as C(e) and called thetimestamp ofe, and is defined as follows:C:H7 Tsuch that the following property is satisfied:for two eventseiandej,ei ej= C(ei)<C(ej).A. Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 20084 / 67 Distributed Computing: Principles, Algorithms, and SystemsA Framework for a System of Logical ClocksThis monotonicity property is called theclock consistency the following condition,for two eventseiandej,ei ej C(ei)<C(ej)the system of clocks is said to bestrongly Logical ClocksImplementation of Logical clocks requires addressing two issues: datastructures local to every process to represent Logical timeand a protocol toupdate the data structures to ensure the consistency processpimaintains data structures that allow it the following twocapabilities.

4 Alocal Logical clock, denoted bylci, that helps processpimeasure its Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 20085 / 67 Distributed Computing: Principles, Algorithms, and SystemsImplementing Logical Clocks Alogical global clock, denoted bygci, that is a representation of processpi slocal view of the Logical global time. Typically,lciis a part protocol ensures that a process s Logical clock, and thus its view of the globaltime, is managed consistently. The protocol consists of thefollowing two rules:R1: This rule governs how the local Logical clock is updated by aprocesswhen it executes an : This rule governs how a process updates its global Logical clock toupdate its view of the global time and global of Logical clocks differ in their representation of Logical time and alsoin the protocol to update the Logical Kshemkalyani and M.

5 Singhal (Distributed Computing) Logical TimeCUP 20086 / 67 Distributed Computing: Principles, Algorithms, and SystemsScalar TimeProposed by Lamport in 1978 as an attempt to totally order events in adistributed domain is the set of non-negative Logical local clock of a processpiand its local view of the global timeare squashed into one integer update the clocks are as follows:R1: Before executing an event (send, receive, or internal), processpiexecutesthe following:Ci:=Ci+d(d>0)In general, every timeR1is executed,dcan have a different value; however,typicallydis kept at Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 20087 / 67 Distributed Computing: Principles, Algorithms, and SystemsScalar TimeR2: Each message piggybacks the clock value of its sender at sending a processpireceives a message with timestampCmsg, it executes thefollowing actions: Ci:=max(Ci,Cmsg) ExecuteR1.

6 Deliver the shows evolution of scalar Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 20088 / 67 Distributed Computing: Principles, Algorithms, and SystemsScalar TimeEvolution of scalar time:p1p2p3123310115 6 72794b189451 Figure : The space-time diagram of a distributed Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 20089 / 67 Distributed Computing: Principles, Algorithms, and SystemsBasic PropertiesConsistency PropertyScalar clocks satisfy the monotonicity and hence the consistency property:for two eventseiandej,ei ej= C(ei)<C(ej).Total OrderingScalar clocks can be used to totally order events in a distributed main problem in totally ordering events is that two or more events atdifferent processes may have identical example in Figure , the third event of processP1and the second eventof processP2have identical scalar Kshemkalyani and M.

7 Singhal (Distributed Computing) Logical TimeCUP 200810 / 67 Distributed Computing: Principles, Algorithms, and SystemsTotal OrderingA tie- breaking mechanism is needed to order such events. A tie is broken asfollows:Process identifiers are linearly ordered and tie among events with identicalscalar timestamp is broken on the basis of their process lower the process identifier in the ranking, the higher the timestamp of an event is denoted by a tuple (t,i) wheretis its time ofoccurrence andiis the identity of the process where it total order relation on two eventsxandywith timestamps(h,i)and(k,j), respectively, is defined as follows:x y (h<kor(h=kandi<j))A.

8 Kshemkalyani and M. Singhal (Distributed Computing) Logical TimeCUP 200811 / 67 Distributed Computing: Principles, Algorithms, and SystemsProperties..Event countingIf the increment valuedis always 1, the scalar time has the followinginteresting property: if eventehas a timestamph, thenh-1represents theminimum Logical duration, counted in units of events, required beforeproducing the evente;We call it the height of the other words,h-1events have been produced sequentially before the eventeregardless of the processes that produced these example, in Figure , five events precede eventbon the longest causalpath ending Kshemkalyani and M.

9 Singhal (Distributed Computing) Logical TimeCUP 200812 / 67 Distributed Computing: Principles, Algorithms, and SystemsProperties..No Strong ConsistencyThe system of scalar clocks is not strongly consistent; thatis, for two eventseiandej, C(ei)<C(ej)6= ei example, in Figure , the third event of processP1has smaller scalartimestamp than the third event of , the former did nothappen before the reason that scalar clocks are not strongly consistent isthat the logicallocal clock and Logical global clock of a process are squashed into one,resulting in the loss causal dependency information among events at example, in Figure , when processP2receives the first message fromprocessP1, it updates its clock to 3, forgetting that the timestamp of thelatest event atP1on which it depends is Kshemkalyani and M.

10 Singhal (Distributed Computing) Logical TimeCUP 200813 / 67 Distributed Computing: Principles, Algorithms, and SystemsVector TimeThe system of vector clocks was developed independently by Fidge, Matternand the system of vector clocks, the time domain is represented by a set ofn-dimensional non-negative integer processpimaintains a vectorvti[ ], wherevti[i] is the local logicalclock ofpiand describes the Logical time progress at [j] represents processpi s latest knowledge of processpjlocal [j]=x, then processpiknows that local time at processpjhasprogressed entire vectorvticonstitutespi s view of the global Logical time and isused to timestamp Kshemkalyani and M.