Chapter 4: Global State And Snapshot Recording Algorithms
Chapter 4: Global State and Snapshot RecordingAlgorithmsAjay Kshemkalyani and Mukesh SinghalDistributed Computing: Principles, Algorithms, and SystemsCambridge University PressA. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20081 / 51
Distributed Computing: Principles, Algorithms, and SystemsIntroductionRecording the global state of a distributed system on-the-fly is an importantparadigm.The lack of globally shared memory, global clock and unpredictable messagedelays in a distributed system make this problem non-trivial.This chapter first defines consistent global states and discusses issues to beaddressed to compute consistent distributed snapshots.Then several algorithms to determine on-the-fly such snapshots are presentedfor several types of networks.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20082 / 51
Distributed Computing: Principles, Algorithms, and SystemsSystem modelThe system consists of a collection of n processes p1 , p2 , ., pn that areconnected by channels.There are no globally shared memory and physical global clock and processescommunicate by passing messages through communication channels.Cij denotes the channel from process pi to process pj and its state is denotedby SCij .The actions performed by a process are modeled as three types of events:Internal events,the message send event and the message receive event.For a message mij that is sent by process pi to process pj , let send(mij ) andrec(mij ) denote its send and receive events.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20083 / 51
Distributed Computing: Principles, Algorithms, and SystemsSystem modelAt any instant, the state of process pi , denoted by LSi , is a result of thesequence of all the events executed by pi till that instant.For an event e and a process state LSi , e LSi iff e belongs to the sequenceof events that have taken process pi to state LSi .For an event e and a process state LSi , e6 LSi iff e does not belong to thesequence of events that have taken process pi to state LSi .For a channel Cij , the following set of messages can be defined based on thelocal states of the processes pi and pjTransit: transit(LSi , LSj ) {mij send(mij ) LSiA. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsVrec(mij ) 6 LSj }CUP 20084 / 51
Distributed Computing: Principles, Algorithms, and SystemsModels of communicationRecall, there are three models of communication: FIFO, non-FIFO, and Co.In FIFO model, each channel acts as a first-in first-out message queue andthus, message ordering is preserved by a channel.In non-FIFO model, a channel acts like a set in which the sender process addsmessages and the receiver process removes messages from it in a randomorder.A system that supports causal delivery of messages satisfies the followingproperty: “For any two messages mij and mkj , if send(mij ) send(mkj ),then rec(mij ) rec(mkj )”.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20085 / 51
Distributed Computing: Principles, Algorithms, and SystemsConsistent global stateThe global state of a distributed system is a collection of the local states ofthe processes and the channels.Notationally, global state GS is defined as,SSGS { i LSi , i ,j SCij }A global state GS is a consistent global state iff it satisfies the following twoconditions :C1: send(mij ) LSi mij SCij rec(mij ) LSj . ( is Ex-ORoperator.)C2: send(mij )6 LSi mij 6 SCij rec(mij )6 LSj .A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20086 / 51
Distributed Computing: Principles, Algorithms, and SystemsInterpretation in terms of cutsA cut in a space-time diagram is a line joining an arbitrary point on eachprocess line that slices the space-time diagram into a PAST and a FUTURE.A consistent global state corresponds to a cut in which every messagereceived in the PAST of the cut was sent in the PAST of that cut.Such a cut is known as a consistent cut.For example, consider the space-time diagram for the computation illustratedin Figure 4.1.Cut C1 is inconsistent because message m1 is flowing from the FUTURE tothe PAST.Cut C2 is consistent and message m4 must be captured in the state ofchannel C21 .A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20087 / 51
Distributed Computing: Principles, Algorithms, and SystemspC1e111p3p4e13e 23e41e31m1e21p2C2e21m2e22e42e23m5m4e34e 33m3e 14e35e42timeFigure 4.1: An Interpretation in Terms of a Cut.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20088 / 51
Distributed Computing: Principles, Algorithms, and SystemsIssues in recording a global stateThe following two issues need to be addressed:I1: How to distinguish between the messages to be recorded in thesnapshot from those not to be recorded.-Any message that is sent by a process before recording itssnapshot, must be recorded in the global snapshot (from C1).-Any message that is sent by a process after recording its snapshot,must not be recorded in the global snapshot (from C2).I2: How to determine the instant when a process takes its snapshot.-A process pj must record its snapshot before processing a messagemij that was sent by process pi after recording its snapshot.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 20089 / 51
Distributed Computing: Principles, Algorithms, and SystemsSnapshot algorithms for FIFO channelsChandy-Lamport algorithmThe Chandy-Lamport algorithm uses a control message, called a markerwhose role in a FIFO system is to separate messages in the channels.After a site has recorded its snapshot, it sends a marker, along all of itsoutgoing channels before sending out any more messages.A marker separates the messages in the channel into those to be included inthe snapshot from those not to be recorded in the snapshot.A process must record its snapshot no later than when it receives a marker onany of its incoming channels.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200810 / 51
Distributed Computing: Principles, Algorithms, and SystemsChandy-Lamport algorithmThe algorithm can be initiated by any process by executing the “MarkerSending Rule” by which it records its local state and sends a marker on eachoutgoing channel.A process executes the “Marker Receiving Rule” on receiving a marker. If theprocess has not yet recorded its local state, it records the state of the channelon which the marker is received as empty and executes the “Marker SendingRule” to record its local state.The algorithm terminates after each process has received a marker on all ofits incoming channels.All the local snapshots get disseminated to all other processes and all theprocesses can determine the global state.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200811 / 51
Distributed Computing: Principles, Algorithms, and SystemsChandy-Lamport algorithmMarker Sending Rule for process i1Process i records its state.2For each outgoing channel C on which a markerhas not been sent, i sends a marker along Cbefore i sends further messages along C.Marker Receiving Rule for process jOn receiving a marker along channel C:if j has not recorded its state thenRecord the state of C as the empty setFollow the “Marker Sending Rule”elseRecord the state of C as the set of messagesreceived along C after j’s state was recordedand before j received the marker along CA. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200812 / 51
Distributed Computing: Principles, Algorithms, and SystemsCorrectness and ComplexityCorrectnessDue to FIFO property of channels, it follows that no message sent after themarker on that channel is recorded in the channel state. Thus, condition C2is satisfied.When a process pj receives message mij that precedes the marker on channelCij , it acts as follows: If process pj has not taken its snapshot yet, then itincludes mij in its recorded snapshot. Otherwise, it records mij in the state ofthe channel Cij . Thus, condition C1 is satisfied.ComplexityThe recording part of a single instance of the algorithm requires O(e)messages and O(d) time, where e is the number of edges in the network andd is the diameter of the network.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200813 / 51
Distributed Computing: Principles, Algorithms, and SystemsProperties of the recorded global stateThe recorded global state may not correspond to any of the global states thatoccurred during the computation.This happens because a process can change its state asynchronously beforethe markers it sent are received by other sites and the other sites record theirstates. But the system could have passed through the recorded global states in someequivalent executions.The recorded global state is a valid state in an equivalent execution and if astable property (i.e., a property that persists) holds in the system before thesnapshot algorithm begins, it holds in the recorded global snapshot.Therefore, a recorded global state is useful in detecting stable properties.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200814 / 51
Distributed Computing: Principles, Algorithms, and SystemsSpezialetti-Kearns algorithmThere are two phases in obtaining a global snapshot: locally recording thesnapshot at every process and distributing the resultant global snapshot to all theinitiators.Efficient snapshot recordingIn the Spezialetti-Kearns algorithm, a markers carries the identifier of theinitiator of the algorithm. Each process has a variable master to keep track ofthe initiator of the algorithm.A key notion used by the optimizations is that of a region in the system. Aregion encompasses all the processes whose master field contains theidentifier of the same initiator.When the initiator’s identifier in a marker received along a channel is differentfrom the value in the master variable, the sender of the marker lies in adifferent region.The identifier of the concurrent initiator is recorded in a local variableid-border -set.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200815 / 51
Distributed Computing: Principles, Algorithms, and SystemsThe state of the channel is recorded just as in the Chandy-Lamport algorithm(including those that cross a border between regions).Snapshot recording at a process is complete after it has received a markeralong each of its channels.After every process has recorded its snapshot, the system is partitioned intoas many regions as the number of concurrent initiations of the algorithm.Variable id-border -set at a process contains the identifiers of the neighboringregions.Efficient dissemination of the recorded snapshotIn the snapshot recording phase, a forest of spanning trees is implicitlycreated in the system. The initiator of the algorithm is the root of a spanningtree and all processes in its region belong to its spanning tree.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200816 / 51
Distributed Computing: Principles, Algorithms, and SystemsEfficient dissemination of the recorded snapshotIf pi receives its first marker from pj then process pj is the parent of processpi in the spanning tree.When an intermediate process in a spanning tree has received the recordedstates from all its child processes and has recorded the states of all incomingchannels, it forwards its locally recorded state and the locally recorded statesof all its descendent processes to its parent.When the initiator receives the locally recorded states of all its descendentsfrom its children processes, it assembles the snapshot for all the processes inits region and the channels incident on these processes.The initiator exchanges the snapshot of its region with the initiators inadjacent regions in rounds.The message complexity of snapshot recording is O(e) irrespective of thenumber of concurrent initiations of the algorithm. The message complexity ofassembling and disseminating the snapshot is O(rn2 ) where r is the numberof concurrent initiations.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200817 / 51
Distributed Computing: Principles, Algorithms, and SystemsSnapshot algorithms for non-FIFO channelsIn a non-FIFO system, a marker cannot be used to delineate messages intothose to be recorded in the global state from those not to be recorded in theglobal state.In a non-FIFO system, either some degree of inhibition or piggybacking ofcontrol information on computation messages to capture out-of-sequencemessages.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200818 / 51
Distributed Computing: Principles, Algorithms, and SystemsLai-Yang algorithmThe Lai-Yang algorithm fulfills this role of a marker in a non-FIFO system byusing a coloring scheme on computation messages that works as follows:1Every process is initially white and turns red while taking a snapshot. Theequivalent of the “Marker Sending Rule” is executed when a process turnsred.2Every message sent by a white (red) process is colored white (red).Thus, a white (red) message is a message that was sent before (after) thesender of that message recorded its local snapshot.Every white process takes its snapshot at its convenience, but no later thanthe instant it receives a red message.34A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200819 / 51
Distributed Computing: Principles, Algorithms, and SystemsLai-Yang algorithm4Every white process records a history of all white messages sent or receivedby it along each channel.5When a process turns red, it sends these histories along with its snapshot tothe initiator process that collects the global snapshot.6The initiator process evaluates transit(LSi , LSj ) to compute the state of achannel Cij as given below:SCij white messages sent by pi on Cij white messages received by pj onCij {send(mij ) send(mij ) LSi } {rec(mij ) rec(mij ) LSj }.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200820 / 51
Distributed Computing: Principles, Algorithms, and SystemsMattern’s algorithmMattern’s algorithm is based on vector clocks and assumes a single initiatorprocess and works as follows:123456The initiator “ticks” its local clock and selects a future vector time s atwhich it would like a global snapshot to be recorded. It then broadcasts thistime s and freezes all activity until it receives all acknowledgements of thereceipt of this broadcast.When a process receives the broadcast, it remembers the value s and returnsan acknowledgement to the initiator.After having received an acknowledgement from every process, the initiatorincreases its vector clock to s and broadcasts a dummy message to allprocesses.The receipt of this dummy message forces each recipient to increase its clockto a value s if not already s.Each process takes a local snapshot and sends it to the initiator when (justbefore) its clock increases from a value less than s to a value s.The state of Cij is all messages sent along Cij , whose timestamp is smallerthan s and which are received by pj after recording LSj .A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200821 / 51
Distributed Computing: Principles, Algorithms, and SystemsMattern’s algorithmA termination detection scheme for non-FIFO channels is required to detectthat no white messages are in transit.One of the following schemes can be used for termination detection:First method:Each process i keeps a counter cntri that indicates the difference between thenumber of white messages it has sent and received before recording itssnapshot.It reports this value to the initiator process along with its snapshot andforwards all white messages, it receives henceforth, to the initiator.PSnapshot collection terminates when the initiator has received i cntrinumber of forwarded white messages.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200822 / 51
Distributed Computing: Principles, Algorithms, and SystemsMattern’s algorithmSecond method:Each red message sent by a process carries a piggybacked value of the numberof white messages sent on that channel before the local state recording.Each process keeps a counter for the number of white messages received oneach channel.A process can detect termination of recording the states of incoming channelswhen it receives as many white messages on each channel as the valuepiggybacked on red messages received on that channel.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200823 / 51
Distributed Computing: Principles, Algorithms, and SystemsSnapshots in a causal delivery systemThe causal message delivery property CO provides a built-in messagesynchronization to control and computation messages.Two global snapshot recording algorithms, namely, Acharya-Badrinath andAlagar-Venkatesan exist that assume that the underlying system supportscausal message delivery.In both these algorithms recording of process state is identical and proceed asfollows :An initiator process broadcasts a token, denoted as token, to every processincluding itself.Let the copy of the token received by process pi be denoted tokeni .A process pi records its local snapshot LSi when it receives tokeni and sendsthe recorded snapshot to the initiator.The algorithm terminates when the initiator receives the snapshot recordedby each process.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200824 / 51
Distributed Computing: Principles, Algorithms, and SystemsSnapshots in a causal delivery systemCorrectnessFor any two processes pi and pj , the following property is satisfied:send(mij ) 6 LSi rec(mij ) 6 LSj .This is due to the causal ordering property of the underlying system asexplained next. Let a message mij be such that rec(tokeni ) send(mij ).Then send(tokenj ) send(mij ) and the underlying causal ordering propertyensures that rec(tokenj ), at which instant process pj records LSj , happensbefore rec(mij ).Thus, mij whose send is not recorded in LSi , is not recorded as received in LSj .Channel state recording is different in these two algorithms and is discussednext.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200825 / 51
Distributed Computing: Principles, Algorithms, and SystemsChannel state recording in Acharya-Badrinath algorithmEach process pi maintains arrays SENTi [1, .N] and RECDi [1, ., N].SENTi [j] is the number of messages sent by process pi to process pj .RECDi [j] is the number of messages received by process pi from process pj .Channel states are recorded as follows:When a process pi records its local snapshot LSi on the receipt of tokeni , itincludes arrays RECDi and SENTi in its local state before sending thesnapshot to the initiator.A. Kshemkalyani and M. Singhal (Distributed Computing)Global State and Snapshot Recording AlgorithmsCUP 200826 / 51
Distributed Computing: Principles, Algorithms, and Sys
Distributed Computing: Principles, Algorithms, and Systems System model At any instant, the state of process pi, denoted by LSi, is a result of the sequence of all the events executed by pi till that instant. For an event e and a process state LSi, e LSi iff e belongs to the sequence of events that have taken process pi to state LS
Part One: Heir of Ash Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26 Chapter 27 Chapter 28 Chapter 29 Chapter 30 .
TO KILL A MOCKINGBIRD. Contents Dedication Epigraph Part One Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Part Two Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18. Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26
DEDICATION PART ONE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 PART TWO Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 .
About the husband’s secret. Dedication Epigraph Pandora Monday Chapter One Chapter Two Chapter Three Chapter Four Chapter Five Tuesday Chapter Six Chapter Seven. Chapter Eight Chapter Nine Chapter Ten Chapter Eleven Chapter Twelve Chapter Thirteen Chapter Fourteen Chapter Fifteen Chapter Sixteen Chapter Seventeen Chapter Eighteen
18.4 35 18.5 35 I Solutions to Applying the Concepts Questions II Answers to End-of-chapter Conceptual Questions Chapter 1 37 Chapter 2 38 Chapter 3 39 Chapter 4 40 Chapter 5 43 Chapter 6 45 Chapter 7 46 Chapter 8 47 Chapter 9 50 Chapter 10 52 Chapter 11 55 Chapter 12 56 Chapter 13 57 Chapter 14 61 Chapter 15 62 Chapter 16 63 Chapter 17 65 .
HUNTER. Special thanks to Kate Cary. Contents Cover Title Page Prologue Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter
Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 . Within was a room as familiar to her as her home back in Oparium. A large desk was situated i
The Hunger Games Book 2 Suzanne Collins Table of Contents PART 1 – THE SPARK Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8. Chapter 9 PART 2 – THE QUELL Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapt
