Ordering and Consistent CutsIntroductionA distributed system is ….Distributed ComputationSo what does this global history as defined tell us?Happened Before Relation (→)Space Time DiagramIs this notion of ordering really important?Global States and CutsExample of a CutIntroduction to consistencySlide 12So what went wrong?So what is a consistent global state?Passive Deadlock DetectionFIFO ChannelsOk let’s now fix consistencyClock ConditionLogical ClocksLamport’s ClocksExample of Logical ClocksObservations on Lamports ClocksVector Clocks ExampleLet’s formalise the ideaSo are Lamport clocks useful only for finding global state?AlgorithmAlgorithm SummaryGlobal State RevisitedRequirementsGlobal StatesWhat exactly is channel stateBasic Algorithm DescriptionSlide 33Comments on AlgorithmConclusionOrdering and Consistent CutsPresented ByBiswanath PandaIntroductionOrdering and global state detection in a “distributed system”Fundamental QuestionsWhat is a distributed system?What is a distributed computation?How can we represent a distributed system?Why are today’s papers so important?A distributed system is ….A collection of sequential processes p1, p2, p3…..pnNetwork capable of implementing communication channels between pairs of processes for message exchangeChannels are reliable but may deliver messages out of orderEvery process can communicate with every other process(may not be directly)There is no reasoning based on global clocksAll kinds of synchronization must be done by message passingDistributed ComputationA distributed computation is a single execution of a distributed program by a collection of processes. Each sequential process generates a sequence of events that are either internal events, or communication eventsThe local history of process pi during a computation is a (possibly infinite) sequence of events hi = ei1, ei2…....A partial local history of a process is a prefix of the local history hin = ei1 , ei2 … einThe global history of a computation is the set H = Ui=1n hiSo what does this global history as defined tell us?It is just the collection of events that have occurred in the systemIt does not give us any idea about the relative times between the eventsAs there is no notion of global time, events can only be ordered based on a notion of cause and effectSo lets formalize this ideaHappened Before Relation (→)If a and b are events in the same process then a → bIf a is the sending of a message m by a process and b is the corresponding receive event then a → bFinally if a → b b → c then a → cIf a → b and b → a then a and b are concurrent→ defines a partial order on the set HSpace Time DiagramGraphical representation of a distributed systemIf there is a path between two events then they are relatedElse they are concurrentIs this notion of ordering really important?Some idea of ordering of events is fundamental to reason about how a system worksGlobal State Detection is a fundamental problem in distributed computingEnables detecting stable properties of a systemHow do we get a snapshot of the system when there is no notion of global time or shared memoryHow do we ensure that that the state collected is consistentUse this problem to illustrate the importance of ordering This will also give us the notion of what is a consistent global stateGlobal States and CutsGlobal State is a n-tuple of local states one for each processCut is a subset of the global history that contains an initial prefix of each local stateTherefore every cut is a natural global stateIntuitively a cut partitions the space time diagram along the time axisA Cut is identified by the last event of each process that is part of the cutExample of a CutIntroduction to consistencyConsider this solution for the common problem of deadlock detectionSystem has 3 processes p1, p2, p3An external process p0 sends a message to each process (Active Monitoring)Each process on getting this message reports its local stateNote that this global state thus collected at p0 is a cutp0 uses this information to create a wait for graphConsider the space time diagram below and the cut C21 2 3 Cycle formedSo what went wrong?p0 detected a cycle when there was no deadlockState recorded contained a message received by p3 which p1 never sentThe system could never be in such a state and hence the state p0 saw was inconsistentSo we need to make sure that application see consistent statesSo what is a consistent global state?A cut C is consistent if for all events e and e’Intuitively if an event is part of a cut then all events that happened before it must also be part of the cutA consistent cut defines a consistent global stateNotion of ordering is needed after all !!   CeeeCe  ''Passive Deadlock DetectionLet’s change our approach to deadlock detection p0 now monitors the system passivelyEach process sends p0 a message when an event occursWhat global state does p0 now seeBasically hell breaks loseFIFO ChannelsCommunication channels need not preserve message orderTherefore p0 can construct any permutation of events as a global stateSome of these may not even be valid (events of the same process may not be in order)Implement FIFO channels using sequence numbersNow we know that we p0 sees constructs valid runsBut the issue of consistency still remains)'()()'()( mdelivermdel ivermsendmsendjjiiOk let’s now fix consistencyAssume a global real-time clock and bound of δ on the message delayDon’t panic we shall get rid of this assumption soonRC(e): Time when event e occursEach process reports to p0 the global timestamp along with the eventDelivery Rule at p0: At time t, deliver all received messages upto t- δ in increasing timestamp orderSo do we have a consistent state now?Clock ConditionYes we do!!e is observed before e’ iff RC(e) < RC(e’)Recall our definition of consistencyTherefore state is consistent iffThis is the clock conditionFor timestamps from a global clock this is obviously trueCan we satisfy it for asynchronous systems?   CeeeCe  '')'()(' eRCeRCee Logical ClocksTurns out that the clock condition can be satisfied in asynchronous systems as well→ is defined such that Clock