Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 54
Текст из файла (страница 54)
We could use a synchronizer for the localclocks, but it is too expensive to do this at every step. Instead, we could use a synchronizerevery so often, say every 1000 steps. Still, in a pure asynchronous system, the worst-casebehavior of this strategy will be poor. This algorithm makes more sense in a setting withsome notion of real-time.21.1.3 ApplicationsIt is not clear that the above algorithms can always be used to implement some ltimeabstraction, which then can be used as a \black box". The problem is that the logical time11In other words, we don't allow Zeno behaviors, in which innite executions take a nite amount of time.266abstraction does not have a clear interface description.
Rather, we'll consider uses of thegeneral idea of logical time. Before we go into more sophisticated applications, we remarkthat both algorithms can be used to support logical time for a system containing broadcastactions, as described above.Banking systemSuppose we want to count the total amount of money in a banking system in which no newmoney is added to or removed from the system, but it may be sent around and received (i.e.,the system satises conservation of money).
The system is modeled as some collection ofIOAs with no external actions, having the local amount of money encoded in the local state,with send actions and receive actions that have money parameters. The architecture is xedin our model the only variation is in the decision of when to send money, and how much.Suppose this system somehow manages to associate a logical time with each event asabove.
Imagine that each node now consists of an augmented automaton that \contains"the original automaton. This augmented automaton is supposed to \know" the logical timeassociated with each event of the basic automaton. In this case, in order to count the totalamount of money in the bank, it suces to do the following.1. Fix some particular time t, known to all the nodes.2. For each node, determine the amount of money in the state of the basic automatonafter processing all events with logical time less than or equal to t (and no later events).3. For each channel, determine the amount of money in all the messages sent at a logicaltime at most t but received at a logical time strictly greater than t.Adding up all these amounts gives a correct total.
This can be argued as follows. Considerany execution of the basic system, together with its logical time assignment. By thereordering result, there's another execution 0 of the same basic system as above and samelogical time assignment, that looks the same to all nodes, and all events occur in logical timeorder. What this strategy does is \cut" execution 0 immediately after time t, and recordthe money in all the nodes, and the money in all the channels.
This simple strategy is thusgiving an instantaneous snapshot of the system state, which gives the correct total amountof money in the banking system.Let us consider how to do this with a distributed algorithm. Each augmented automatoni is responsible for overseeing the work of basic automaton i. Augmented automaton i isassumed able to look inside basic automaton i to see the amount of money. (Note that thisis not ordinary IOA composition: the interface abstractions are violated by the coupling.) It267is also assumed to know the logical time associated with each event of the basic automaton.The augmented automaton i is responsible for determining the state of the basic automatonat that node, plus the states of all the incoming channels.The augmented automaton i attaches the logical time of each send event to the messagebeing sent.
It records the basic automaton state as follows. Automaton i records the stateafter each step, until it sees some logical time greater than t. Then it \backs up" onestep and returns the previous state. For recording the channel state, we need to know themessages that are sent at a logical time (at the sender) at most t and received at a logicaltime (at the receiver) strictly greater than t. So as soon as an event occurs with logicaltime exceeding t (that is, when it records the node state), it starts recording messagescoming in on the channel.
It continues recording them as long as the attached timestampis no more than t. Note: to ensure termination, we need to assume that each basic nodecontinues sending messages every so often, so that its neighbors eventually get somethingwith timestamp strictly larger than t. Alternatively, the counting protocol itself could addsome extra messages to determine when all the sender's messages with attached time at mostt have arrived.We remark that the augmented algorithm has the nice property that it doesn't interferewith the underlying operation of the basic system.General SnapshotThis strategy above can, of course, be generalized beyond banks, to arbitrary asynchronoussystems. Suppose we want to take any such system that is running, and determine a globalstate at some point in time.
We can't actually do this without stopping everything in thesystem at one time (or making duplicate copies of everything). It is not practical in a realdistributed system (e.g., one with thousands of nodes) to really stop everything: it couldeven be impossible. But for some applications, it may be sucient to get a state that just\looks like" a correct global state, as far as the nodes can tell. (We shall see some suchapplications later.) In this case, we can use the strategy described above.Simulating a Single State MachineAnother use, mentioned but not emphasized in Lamport's paper (but very much emphasizedby him in the ensuing years) is the use of logical time to allow a distributed system tosimulate a centralized state machine, i.e., a single object.
The notion of an object thatworks here is a very simple one { essentially, it is an IO automaton with input actions onlywe require that there be only one initial value and that the new state be determined by theold state and the input action. (This may not seem very useful at rst glance, but it can be268used to solve some interesting synchronization problems, e.g., we will see how to use it tosolve mutual exclusion. It's also a model for a database with update operations.)Suppose now that there are n users supplying inputs (updates) at the n node processes ofthe network. We would like them all to apply their updates to the same centralized object.We can maintain one copy of this object in one centralized location, and send all the updatesthere.
But suppose that we would like all the nodes to have access to (i.e., to be able to read)the latest available state of the object. (E.g., suppose that reads are more frequent thanwrites, and we want to minimize the amount of communication.) This suggests a replicatedimplementation of the object, where each node keeps a private copy we can broadcast allthe updates to all the nodes, and let them all apply the updates to their copies.
But theyneed to update their copies in the same way, at least eventually. If we just broadcast theupdates, nothing can stop dierent nodes from applying them in dierent orders. We requirea total order of all the updates produced anywhere in the system, known to all the nodes,so that they can all apply them in the same order. Moreover, there should only be nitelymany updates ordered before any particular one, so that all can eventually be performed.Also, a node needs to know when it's safe to apply an update | this means that no furtherupdates that should have been applied before (i.e., before the one about to be applied) willever arrive.
We would like the property of monotonicity of successive updates submitted bya particular node, in order to facilitate this property.The answer to our problems is logical time. When a user submits an update, the associated process broadcasts it, and assigns it a timestamp , which is the logical time assigned tothe broadcast event for the update. (If a node stops getting local updates as inputs, it shouldstill continue to send some dummy messages out, just to keep propagating information aboutits logical time.) Each node puts all the updates it receives, together with their timestamps,in a \request queue", not yet applying them to the object.
(Note: this queue must includeall the updates the node receives in broadcasts by other nodes, plus those the node sends inits own broadcasts.) The node applies update u if the following conditions are satised.1. Update u has the smallest timestamp of any request on the request queue.2. The node has received a message (request or dummy) from every node with send timeat least equal to the timestamp of u.Condition 2 and the FIFOness of the channels guarantee that the node will never receiveanything with smaller timestamp than this rst update.
Furthermore, any node eventuallysucceeds in applying all updates, because logical time keeps increasing at all nodes. Notethat we didn't strictly need Property 3 of logical time (relating the times of message sendand receive) here for correctness. But something like that is important for performance.269Example: Banking distributed database. Suppose each node is a bank branch, andupdates are things like deposit, withdraw, add-interest, withdraw-from-checking-if-sucientfunds-else-from-savings, etc.
Note that in some of these cases, the order of the updatesmatters. Also suppose that all the nodes want to keep a recent picture of all the bankinformation (for reading, deciding on which later updates should be triggered at that branch,etc.). We can use logical time as above to simulate a centralized state machine representingthe bank information.Note that this algorithm is not very fault-tolerant. (Also, in general, it does not seemvery ecient.
But it can sometimes be reasonable | see the mutual exclusion algorithmbelow.)21.2 Simulating Shared MemoryIn this section we consider another simplifying strategy for asynchronous networks. We usethis strategy to simulate (instantaneous) shared memory algorithms.The basic idea is simple. Locate each shared variable at some node. Each operationgets sent to the appropriate node, and the sending process waits for a response.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
