Ordering of Events in Distributed SystemsMotivation: Time, Clocks, OrderingSlide 3TerminologyPartial OrderingSpace-Time DiagramLogical ClocksImplementation of Logical ClocksLogical Clocks ExampleSlide 10Total OrderingDistributed State MachinesMutual Exclusion ExampleSlide 14Physical ClocksConclusionsDistributed SnapshotsSystem ModelDistributed Snapshot AlgorithmIntuition with Logical TimeMarker RulesBanking ExampleSlide 23Slide 24Slide 25Slide 26Slide 27Properties of Recorded Global StateSlide 29Slide 30Ordering of Events in Distributed SystemsUNIVERSITY of WISCONSIN-MADISONComputer Sciences DepartmentCS 739Distributed SystemsAndrea C. Arpaci-DusseauTwo papers:• Time, Clocks, and the Ordering of Events in a Distributed System, Lamport, 1978• Distributed Snapshots: Determining Global States of Distributed Systems, Chandy and Lamport, 1985Motivation: Time, Clocks, OrderingTo develop distributed algorithms, want all participants see messages in same order (if want same decisions!)How can distributed nodes agree on order of messages?Process AProcess BNaïve: Each process believes sent message firstMotivation: Time, Clocks, OrderingWhen does an event precede (“happen before”) another in a distributed system?•Sometimes impossible to tell; sometimes it doesn’t matter–If event A occurs on machine A,and event B occurs on machine B,but there is no communication between A and B, then did event A or event B happen first???How can a process identify which events happened before others?•Logical clocksTerminologyDistributed system: A collection of distinct processes which are spatially separated and which communicate with one another by exchanging messages•How does this differ from our previous definitions?Process: A sequence of events (instructions, sending messages, receiving messages)•The events within a process have a total orderingPartial OrderingHappened before: ->Rules for ordering events a and b1) if a and b are events in same process and a comes before b, then a->b2) if a is the sending of a message by a process and b is receiving that message, then a->b3) if a->b and b->c then a->ca->b: It is possible for a to causally affect bConcurrent: ‡>•if a ‡> b and b ‡> a, then do not know ordering of a and b•It is not possible for a to causally affect bSpace-Time DiagramTimep1p2p3p4q1q2q3q4q5q6q7r1r2r4r3What is the relationship between (q3,p3)? (p1,q3)? (p2,q3)? (q3,r4)? (r1,q6)?PQ RLogical ClocksAbstract view: Logical clock is a way to assign a number to an event to express ordering•No relation between logical clock and physical timeClock Ci for process Pi is a function that assigns a number Ci(a) to any event a in PiClock condition: For any events a, b:if a->b, then C(a) < C(b)Converse condition does not hold •Can’t say concurrent events have same logical timeIf C(a) < C(b) can’t conclude a->bImplementation of Logical ClocksC1.•If a & b are in Pi & a before b, then Ci(a) < Ci(b)IR1. (Implementation Rule)•Each process Pi increments Ci between any two successive eventsC2. •If a is sent by Pi and b is received by Pj, then Ci(a) < Cj(b)IR2. •(a) If event a is the sending of message m by process Pi, then m contains a timestamp Tm=Ci(a)•(b) Upon receiving m, process Pj sets Cj greater than or equal to its presents value and greater than Tm.Logical Clocks Examplep1p2p3p4q1q2q3q4q5q6q7r1r2r4r3What logical clock values are possible? Assume initial C(p1)=5, C(q1)=50, C(r1)=2Logical Clocks Examplep1p2p3p4q1q2q3q4q5q6q7r1r2r4r3What logical clock values are possible? Assume initial C(p1)=5, C(q1)=50, C(r1)=25 25051526525354555635556575356Total OrderingUse logical clocks to obtain total ordering across all processes and eventsa => b if and only if:•1) Ci(a) < Cj(b) OR•2) Ci(a) = Cj(b) and Pi < Pj (i.e., use process ids to break ties)Partial ordering is unique, but total ordering is not!•Concurrent operations can go in any order•Total ordering depends upon implementation of each Ci()•Total ordering depends upon tie breaking rulesDistributed State MachinesEach process runs same distributed algorithmRelies upon total ordering of requests•Agreed upon by all participants•Can be used to ensure all see events (inputs) in same order and therefore make same decisionsIdea: •All requests are time-stamped, responses (acks) are time-stamped too•Send time-stamped request to all processes•Handle next request in total order–To know next request, must have received greater timestamp from all possible participants–Problems?Example: Mutual exclusionMutual Exclusion ExampleABC D1102030Request queue:Scenario: A and C want resourceA and C each send request before see other’s (concurrent requests)C sends request out earlier in “physical time”How will all nodes agree who should get resource?Mutual Exclusion ExampleABC D1102030212121223122223323222Request queue: A - 2, C - 21Physical ClocksMotivation: Can observe anomalous behavior if other communication channels exist between processes•Useful to have physical clock with meaning in physical worldSynchronize independent physical clocks, each running at slightly different rates (skew)Implementation Idea:•Send timestamp with each message •Receiver may update clock to timestamp+minimal network delay–Clock must always increaseLots of work in this areaConclusionsDistributed, replicated state machines useful for tolerating faults Need to construct total ordering of events to obtain same results everywhereLogical clocks very simple to implementWill see logical clocks used to update replicasDistributed SnapshotsGoal•Want to record global state of distributed system (i.e., state of each process, state of each communication channel)•Useful so can observe system properties–Computation terminated?–System deadlocked?–Number of tokens?Complication:•Distributed system has no shared state nor shared clock•Cannot record global state simultaneously everywhereDistributed snapshot: Record local state at different times and combine into meaningful picture•Obtain cut in logical time, remain consistent by preserving logical ordering (if not ordering in physical time)System ModelDistributed system: Finite set of processes and channels; described by graphProcesses•Set of states, initial state, set of eventsChannels•FIFO, error-free, infinite buffers, arbitrary but finite delay•State: Sequence of messages sent but not yet receivedDistributed Snapshot AlgorithmGoal: Record local state (each