Distributed Systems: Time and Mutual ExclusionDistributed SystemsTodayWhat time is it?But what does time “mean”?Event OrderingLamport’s approachDrawing time-line pictures:Slide 9Slide 10Slide 11Slide 12Slide 13Happens before “relation”Logical clocksRules for managing logical clocksTime-line with LT annotationsSlide 18Total ordering?Partial OrderingTotal Ordering?Logical Timestamps w/ Process IDDistributed Mutual Exclusion (DME)SolutionCDME: Centralized ApproachProblems of CDMEDDME: Fully Distributed ApproachDDME: Fully Distributed Approach (Cont.)Problems of DDMEToken PassingProblems of Token PassingCompare: Number of Messages?Compare : StarvationSummaryDistributed Systems: Time and Mutual Exclusion2Distributed SystemsDefinition:Loosely coupled processors interconnected by network•Distributed system is a piece of software that ensures:–Independent computers appear as a single coherent system•Lamport: “A distributed system is a system where I can’t get my work done because a computer has failed that I never heard of”3Today•What is the time now?•Distributed Mutual Exclusion4What time is it?•In distributed system we need practical ways to deal with time–E.g. we may need to agree that update A occurred before update B–Or offer a “lease” on a resource that expires at time 10:10.0150 –Or guarantee that a time critical event will reach all interested parties within 100ms5But what does time “mean”?•Time on a global clock?–E.g. with GPS receiver•… or on a machine’s local clock–But was it set accurately?–And could it drift, e.g. run fast or slow?–What about faults, like stuck bits?•… or could try to agree on time6Event Ordering•Fundamental Problem: distributed systems do not share a clock–Many coordination problems would be simplified if they did (“first one wins”)•Distributed systems do have some sense of time–Events in a single process happen in order–Messages between processes must be sent before they can be received–How helpful is this?7Lamport’s approach•Leslie Lamport suggested that we should reduce time to its basics–Time lets a system ask “Which came first: event A or event B?”–In effect: time is a means of labeling events so that…•If A happened before B, TIME(A) < TIME(B)•If TIME(A) < TIME(B), A happened before B8Drawing time-line pictures:pmsndp(m)qrcvq(m) delivq(m)D9Drawing time-line pictures:•A, B, C and D are “events”. –Could be anything meaningful to the application–So are snd(m) and rcv(m) and deliv(m)•What ordering claims are meaningful?pmACBsndp(m)qrcvq(m) delivq(m)D10Drawing time-line pictures:•A happens-before B, and C happens-before D–“Local ordering” at a single process–Write and pqmACBrcvq(m) delivq(m)sndp(m)BAp→DCq→D11Drawing time-line pictures:•sndp(m) also happens-before rcvq(m)–“Distributed ordering” introduced by a message–WritepqmACBrcvq(m) delivq(m)sndp(m))m(rcv)m(sndqMp→D12Drawing time-line pictures:•A happens-before D–Transitivity: A happens-before sndp(m), which happens-before rcvq(m), which happens-before DpqmDACBrcvq(m) delivq(m)sndp(m)13Drawing time-line pictures:•Does B happen before D?•B and D are concurrent–Looks like B happens first, but D has no way to know. No information flowed…pqmDACBrcvq(m) delivq(m)sndp(m)14Happens before “relation”•We’ll say that “A happens-before B”, written AB, ifAPB according to the local ordering, orA is a snd and B is a rcv and AMB, orA and B are related under the transitive closure of rules (1) and (2)•So far, this is just a mathematical notation, not a “systems tool”15Logical clocks•A simple tool that can capture parts of the happens before relation•First version: uses just a single integer–Designed for big (64-bit or more) counters–Each process p maintains LogicalTimestamp (LTp), a local counter–A message m will carry LTm16Rules for managing logical clocks•When an event happens at a process p it increments LTp. –Any event that matters to p–Normally, also snd and rcv events (since we want receive to occur “after” the matching send)•When p sends m, set–LTm = LTp•When q receives m, set–LTq = max(LTq, LTm)+117Time-line with LT annotations•LT(A) = 1, LT(sndp(m)) = 2, LT(m) = 2•LT(rcvq(m))=max(1,2)+1=3, etc…pqmDACBrcvq(m) delivq(m)sndp(m)LTq0 0 0 1 1 1 1 3 3 3 4 5 5LTp0 1 1 2 2 2 2 2 2 3 3 3 318Logical clocks•If A happens-before B, AB,then LT(A)<LT(B)•But converse might not be true:–If LT(A)<LT(B) can’t be sure that AB –This is because processes that don’t communicate still assign timestamps and hence events will “seem” to have an order19Total ordering?•Happens-before gives a partial ordering of events•We still do not have a total ordering of events20Partial OrderingPi ->Pi+1; Qi -> Qi+1; Ri -> Ri+1R0->Q4; Q3->R4; Q1->P4; P1->Q221Total Ordering?P0, P1, Q0, Q1, Q2, P2, P3, P4, Q3, R0, Q4, R1, R2, R3, R4P0, Q0, Q1, P1, Q2, P2, P3, P4, Q3, R0, Q4, R1, R2, R3, R4P0, Q0, P1, Q1, Q2, P2, P3, P4, Q3, R0, Q4, R1, R2, R3, R422 Logical Timestamps w/ Process ID•Assume each process has a local logical clock that ticks once per event and that the processes are numbered–Clocks tick once per event (including message send)–When send a message, send your clock value–When receive a message, set your clock to MAX( your clock, timestamp of message + 1) •Thus sending comes before receiving•Only visibility into actions at other nodes happens during communication, communicate synchronizes the clocks–If the timestamps of two events A and B are the same, then use the network/process identity numbers to break ties. •This gives a total ordering!23Distributed Mutual Exclusion (DME) •Example: Want mutual exclusion in distributed setting–The system consists of n processes; each process Pi resides at a different processor–Each process has a critical section that requires mutual exclusion•Problem: We can no longer rely on just an atomic test and set operation on a single machine to build mutual exclusion primitives•Requirement–If Pi is executing in its critical section, then no other process Pj is executing in its critical section.24Solution•We present three algorithms to ensure the mutual exclusion execution of processes in their critical sections. –Centralized Distributed Mutual Exclusion (CDME)–Fully Distributed Mutual Exclusion (DDME)–Token
View Full Document
Unlocking...