Lamport’s ClocksOriginal Document15-410 Gratuitous Quote of the DayLife Made SimpleTiming is EverythingDistributed SystemHappened Before () Partial OrderConcurrencySpace-Time DiagramClock ConditionLocal ClocksSufficient SubconditionsClock “Ticks”RedrawingSlide 15TimestampsImplementation RulesTotal OrderingMutual Exclusion Example GoalsCentralized Scheduling Fails!Flooding AlgorithmAlgorithmState MachinesLamport’s ClocksDavid EckhardtBruce Maggs2Original Document315-410 Gratuitous Quote of the Day"There have been members of the Maggs family in south east Suffolk since the great subsidy of 1327 but they were of no great distinction either then or afterwards." -- from Allan Farquar Bottomley, "Introduction," in the Southwold Diary of James Maggs, 1818-1876, edited by Allan Farquar Bottomley, Volume I - 1818-1848, (Suffolk: Published for the Suffolk Records Society by the Boydell Press, 1983), p.1.4Life Made Simple•Global clocks simplify protocol design.•E.g., first-come first-serve resource allocation.•Bruce: My watch is synchronized to the U.S. atomic clock!5Timing is Everything•“Time is relative, or did I misread Einstein?” - Dan Bern (irreverent songwriter)•Even in one inertial reference frame, can’t built an “arbiter”.Which button was pressed first?6Distributed System•A collection of processes that exchange messages.•A process consists of a sequence of events.•Sending and receiving messages are two types of events.7Happened Before () Partial Order1. If a and b are events in the same process and a occurs before b, then a b2. If a is the sending of a message by one process and b is the receiving of a message by another, then a b3. If a b and b c, then a c8Concurrency•Two events a and b are said to be concurrent if a b and b a//9Space-Time Diagram10Clock Condition•If a b then C(a) < C(b).•Notice that converse cannot hold: p2, p3, and q3 are concurrent in space-time diagram, would all have to happen at same time. But p2 p3.11Local Clocks•Counter Ci at process Pi•Ci(a) is value of Ci when a occurs at Pi•C(a) = Ci(a) if a occurs at process Pi12Sufficient Subconditions1. If a and b are events in Pi and a comes before b, then Ci(a) < Ci(b).2. If a is the sending of a message from Pi and b is the receiving of the message by Pj, then Ci(a) < Cj(b).13Clock “Ticks”14Redrawing1515-410 Gratuitous Quote of the Day•"First, computer software and hardware are the most complex and rapidly developing intellectual creations of modem man." - p. iii, Internet and Computer Law, P. B. Maggs, J. T. Soma, and J. A. Sprowl, 200116Timestamps•When process Pi sends a message, it attaches a timestamp Tm.17Implementation Rules•Each process Pi increments Ci between any two successive events.•Regarding messages,•(a) if event a is the sending of a message m by process Pi, then m contains timestamp Tm = Ci(a).•(b) upon receiving m, process Pj sets Cj greater than or equal to its own value and greater than Tm18Total Ordering•If a is an event in Pi and b in Pj, then a b if and only if either•Ci(a) < Cj(b) or•Ci(a) = Cj(b) and Pi < Pj•(Assume an ordering on the processes.)19Mutual Exclusion Example Goals•A process that has been granted a resource must release it before it can be granted to another process.•Different requests for the resource must be granted in the order (with respect to ) in which they are made.•If every processes that is granted a resource eventually releases it, then every request is eventually granted.20Centralized Scheduling Fails!•P1 issues a resource request to P0.•P1 tells P2, “I just issued a resource request.”•P2 receives the message.•P2 issues a resource request to P0.•P2’s message arrives first, P0 grants request to P2.21Flooding Algorithm•Broadcast every request to every process.•Assume all messages reach their destinations.•Assume in-order delivery of messages.22Algorithm•To request resource, Pi sends “Tm:Pi requests resource” to all other processes, puts request on local queue.•On receiving “Tm:Pi requests resource”, Pj puts on queue and sends timestamped acknowledgement•To release resource, Pi removes from queue and sends “Pi releases resource” to all other processes•When Pj receives “Pi releases resource”, removes Pi requests from queue•Pi granted resource when Tm:Pi request in queue is ordered by before any other request, and Pi has received a message with time stamp larger than Tm from all others23State Machines•All processes can simulate identical state machines.•Inputs are ordered resource requests and releases.•State indicates which process (if any) has
View Full Document
Unlocking...