Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 59
Текст из файла (страница 59)
By \global state" we mean a state for each process and each FIFO channel. The\consistency", roughly speaking, requires that the output is a global state that \could have"occurred at a xed moment in time.We make the denition of the problem more precise using the notion of logical timediscussed in the last lecture. Recall the denition of logical time: it is possible to assign aunique time to each event, in a way that is increasing at any given node, and such that sendsprecede receives, and only nitely many events precede any particular event. Clearly, a givenexecution can get many logical time assignments. A consistent global state is one that arisesfrom any particular logical time assignment and a particular real time t.
For this assignmentand this t, there is a well-dened notion of what has happened up through (and including)time t. We want to include exactly this information in the snapshot: states of nodes afterthe local events up through time t, and the states of channels at time t (i.e., those messagessent by time t and not received by time t, in the order of sending). See Figure 22.9 for anexample.We can stretch and shrink the execution to align corresponding times at dierent nodes,and the information in snapshot is just the states of nodes and channels at the t-cut.Because we might have to shrink and stretch the execution, it is not necessarily true thatthe state which is found actually occurs at any point in the execution. But, in a sense, this291tFigure 22.9: t is a logical time cut.doesn't matter: it \could have" occurred, i.e., no process can tell locally that it didn't occur.Actually, we would like more than just any consistent global state | we would like onethat is fairly recent (e.g., we want to rule out the trivial solution that always returns theinitial global state).
For instance, one might want a state that reects all the events thathave actually occurred (in real time) before the invocation of the snapshot algorithm. So wesuppose that the snapshot is initiated by the arrival of a snap input from the outside worldat some nonzero number of the nodes (but only once at each node). (We do not impose therestriction that the snapshot must originate at a single node as in the diusing computationproblem. Also, the underlying computation is not necessarily diusing.)ApplicationsA simple example is a banking system, where the goal is to count all the money exactlyonce.
More generally, we have the problem of stable property detection. Formally, we saythat a property of global states is stable if it persists, i.e., if it holds in some state, then itholds in any subsequent state. For instance, termination, the property of all the nodes beingin quiescent states and the channels being empty, is a stable property.
Also, (unbreakable)deadlock, where a cycle of nodes are in states where they are waiting for each other, is astable property.The AlgorithmThe architecture is similar to the one used above for the termination-detection algorithm{ the underlying Ai is augmented to give pi with certain additions that do not aect theunderlying automaton's behavior.We have already sketched one such algorithm, based on an explicit logical time assignment. We now give another solution, by Chandy and Lamport.
The algorithm is very much292like the snapshot based on logical time, only it does away with the explicit logical time.The idea is fairly simple. Each node is responsible for snapping its own state, plus thestates of the incoming channels. When a node rst gets a snap input, it takes a snapshot ofthe state of the underlying algorithm. Then it immediately puts a marker message in eachof its outgoing channels, and starts to record incoming messages in order to snap each of itsincoming channels.
This marker indicates the dividing line between messages that were sentout before the local snap and messages sent out after it. For example, if this is a bankingsystem, and the messages are money, the money before the marker was not included in thelocal snap, but the money after the marker was.A node that has already snapped just records these incoming messages, until it encountersthe marker, in which case it stops recording. Thus, the node has recorded all the messagessent by the sender before the sender did its local snap. Returning to the banking systemexample, in this case the recipient node has counted all the money that was sent out beforethe sender did its snap and thus not counted by the sender.There is one remaining situation to consider: suppose that a node receives a markermessage before it has done its own local snap (because it has not received a snap input).Then immediately upon receiving the rst marker , the recipient snaps its local state, sendsout its markers, and begins recording the incoming channels.
The channel upon which it hasjust received the marker is recorded as empty, however.Modeling. It is not completely straightforward to model a snapshot system. The subtletyis in the atomicity of the snapping and marker sending steps. To do this much atomically,we seem to need to modify the underlying algorithm in slightly more complicated ways thanfor the Dijkstra-Scholten algorithm { possibly by blocking some messages from being sentby Ai while the markers are being put into the channels. This really means interfering withthe underlying algorithm, but, roughly speaking, we do not interfere by \too much".The code is given in Figure 22.10.Correctness. We need to argue that the algorithm terminates, and that when it does, itgives a consistent global state (corresponding to some xed logical time).Termination.
We need strong connectivity to prove termination. As soon as the snapinput occurs, the recipient node does a local snapshot, and sends out markers. Every timeanyone gets a marker, it snaps its state if it hasn't already. The markers thus eventuallypropagate everywhere, and everyone does a local snapshot. Also, eventually the nodes willnish collecting the messages on all channels (when they receive markers).Consistency.
We omit details. The idea is to assign a logical time to each event of theunderlying system, by means of such an assignment for the complete system. We do this in293New state components:status 2 fstart snapping reported g, initially startsnap-state, a state of A or nil, initially nilfor each neighbor j : channel-snapped(j ), a Boolean, initially false , andsend (j ), snap-channel(j ), FIFO queues of messages, initially empty.iActions:New action snapEect: if status = start thensnap-state gets the state of Astatus snappingfor all j 2 neighbors , add marker to send (j )iReplace send (m) actions of A with internal-send actions, which put m at the end of send (j ).i jiNew action send (m)Precondition: m is rst on send (j )Eect: remove rst element of send (j )i jreceive (m), m a message of ANew Eect: if status = snapping and channel ; snapped (j ) = false thenadd m to snap-channel(j )j iiNew action receive (marker )Eect: if status = start thensnap-state gets the state of Astatus snappingfor all j 2 neighbors , add marker to send (j )channel-snapped(j ) truej iiNew action report-snapshot(s C ), where s is a node state, and C is the states of incoming linksPrecondition: status = snappingfor all j 2 neighbors , channel-snapped(j ) = trues = snap-statefor all j 2 neighbors , C (j ) = snap-channel(j )Eect: status reportedFigure 22.10: The snapshot algorithm, code for process i.294such a way that the same time t (with ties broken by indices) is assigned to each event atwhich a node snaps its local state.
The fact that we can do this depends on the fact thatthere is no message sent at one node after the local snap and arriving at another node beforeits local snap. (If a message is sent after a local snap, it follows the marker on the channelthen when the message arrives, the marker will have already arrived, and so the recipientwill have already done its snapshot.) It is obvious that what is returned by each node isthe state of the underlying algorithm up to time t.
We must also check that the channelrecordings give exactly the messages \in transit at logical time t", i.e., the messages sentafter the sender's snap and received before the receiver's snap.Some simple examples. We again use the bank setting. Consider a two-dollar, two-nodebanking system, where initially each node, i and j , has one dollar.
The underlying algorithmhas some program (it doesn't matter what it is) that determines when it sends out somemoney. Consider the following execution (see Figure 22.11).#1i(1)1#10ji1#(2)11ji(3)101ji(4)#0j01i01jFigure 22.11: Execution of a two-node bank system. The nal snapshot is depicted belowthe intermediate states.1. snap i occurs, i records the state of the bank ($1), puts a marker in the buer to sendto j , and starts recording incoming messages2. i puts its dollar in the buer to send to j , behind the marker,3. j sends its dollar to i, i receives it and records it in its location for recording incomingmessages.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
