Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf), страница 76

Consider the following simple \majority-voting" algorithm for implementing a multiwriter multireader register, in majority snapshot shared memory model. In this model,the memory consists of a single vector object, one position per writer process, with eachposition containing a pair consisting of a value v and a positive integer timestamp t.Each read operation instantaneously reads any majority of the memory locations, andreturns the value associated with the largest timestamp.

Each write operation instantaneously reads any majority of the memory locations, determines the largest timestampt, and writes the new value to any majority of the memory locations, accompanied bytimestamp t + 1.Use the lemma proved in class (Lecture 15) to sketch a proof that this is a correctimplementation of an atomic multiwriter multireader register.3.

Show that every exclusion problem can be expressed as a resource problem.4. Show that Lamport's Construction 1, when applied to atomic registers, does not necessarily give rise to an atomic register.3716.852J/18.437J Distributed AlgorithmsHandout 29November 12, 1992Homework Assignment 9Due: Thursday, November 19Exercises1. Give an explicit I/O automaton with a single-writer multi-reader user interface, thatpreserves user well-formedness (alternation of requests and responses), whose fair wellformed behaviors contain responses for all invocations, and whose well-formed externalbehaviors are exactly those that are legal for a regular read/write register.

Do this alsofor a safe read/write register.2. Extend the Burns lower bound on the number of messages needed to elect a leader inan asynchronous ring so that it applies to rings whose sizes are not powers of two.3. Give an explicit algorithm that allows a distinguished leader node i in an arbitraryconnected network graph G to calculate the exact total number of nodes in G.

Sketcha proof that it works correctly.04. Consider a \banking system" in which each node of a network keeps a number indicating an amount of money. We assume, for simplicity, that there are no externaldeposits or withdrawals, but messages travel between nodes at arbitrary times, containing money that is being \transferred" from one node to another. The channelspreserve FIFO order. Design a distributed network algorithm that allows each nodeto decide on (i.e., output) its own balance, so that the total of all the balances is thecorrect amount of money in the system.

To rule out trivial cases, we suppose that theinitial state of the system is not necessarily \quiescent", i.e., there can be messages intransit initially.The algorithm should not halt or delay transfers \unnecessarily". Give a convincingargument that your algorithm works.3726.852J/18.437J Distributed AlgorithmsHandout 31November 19, 1992Homework Assignment 10Due: Thursday, December 3Exercises1.

(This question is open ended, and we haven't worked it out entirely.) Compare theoperation of the Gallager-Humblet-Spira spanning tree algorithm to that of the synchronous version discussed earlier in the course. E.g., is there any relationship betweenthe fragments produced in the two cases? (Perhaps such a connection can be used ina formal proof.)2. Design (outline) an asynchronous algorithm for a network with a leader node i , thatallows i to discover and output the maximum distance d from itself to the furthestnode in the network.

The algorithm should work in time O(d). What is the messagecomplexity?003. Consider a square grid graph G, consisting of n n nodes. Consider a partition Pkinto k equal-sized clusters, obtained by dividing each side into k equal intervals.

Interms of n and k, what are the time and message complexities of synchronizer basedon partition Pk ?24. Obtain the best upper bound you can for an asynchronous solution to the k-sessionproblem.3736.852J/18.437J Distributed AlgorithmsHandout 33December 3, 1992Homework Assignment 11Due: Thursday, December 10Exercises1. Develop a way of simulating single-writer multi-reader shared memory algorithms in anasynchronous network your method should be based on caching, where readers keeplocal copies of all the variables and just read their local copies (if possible).

The writer,however, needs to carry out a more complicated protocol in order to write. Describeappropriate protocols for the writer (and also for the reader, if the local copy is notavailable), in order to simulate instantaneous read/write shared memory. Be sure toguarantee that each process' invocations eventually terminate.Outline why your algorithm works correctly.2. \Optimize" the mutual exclusion algorithm described in class, based on Lamport'sstate machine simulation strategy, in order not to keep all the messages ever receivedfrom all other processes.3.

Prove the following invariant for the Dijkstra-Scholten termination detection algorithm.All non-idle nodes form a tree rooted at the node with status leader, where the treeedges are given by parent pointers.4. In the shortest paths problem, we are given a graph G = (V E ), with weights w(e) > 0for all e 2 E , and a distiguished node i 2 V . The objective is to compute, at each node,its weighted distance from i .

Consider the Bellman-Ford algorithm for synchronousnetworks dened as follows. Each node i maintains a non-negative distance i variable.The algorithm proceeds in rounds as follows. At each round, all the nodes send totheir neighbors the value of their distance variable. The distinguished node i hasdistance = 0 xed, and all other nodes i assign, at each round,000distance i (jminfdistance j + w(j i)g :i)2EAssume that the state of a node consists only of its distance variable. Prove that thisalgorithm is self-stabilizing.374AppendixNotes for extra lectures6.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchJanuary 5, 1993Lecture 26A.1 Implementing Reliable Point-to-Point Communication in terms of Unreliable ChannelsIn our treatment of asynchronous networks, we have mostly dealt withthe fault-free case.Exceptions: self-stabilization (single arbitrary failure)processor stopping faults and Byzantine faults, for consensusNow emphasize failures, but in a very special case { a two-nodenetwork.The problem to be considered is reliable communication between usersat two nodes.Messages are sent by some user at one node, and are supposed to bedelivered to a user at the other.Generally want this delivery to be reliable { FIFO, exactly once each.The sender and receiver nodes are I/O automata.The two channels inside are generally not our usual reliable channels,however.They may have some unreliability properties, e.g.,loss of packetsduplicationreordering.However, we don't normally allow worse faults such as manufacturing ofcompletely bogus messages.375We also don't allow total packet loss { e.g., have a livenessassumption that says something like:\If innitely many packets are sent, then innitely many ofthem are delivered."Have to be careful to state this right { since we are consideringduplication of packets, it's not enough just to say that innitelymany sends imply innitely many receives { we want innitely manyof the dierent send events to have \corresponding" receive events.(We don't want innitely many receives of some earlymessage, while innitely many new messages keep being inserted.)Can usually formalize the channels as I/O automata, (using IOA fairnessto express the liveness condition) but it may be more naturaljust to specify their allowable external behavior(in the form of a \cause" function from packet receipt events topacket send events satisfying certain properties).Later, we will want to generalize the conditions to utilize a\port structure", and say that the channel exhibits FIFO behaviorand liveness with respect to each port separately.

Amounts to acomposition of channels, one for each pair of matching ports.A.1.1 Stenning's ProtocolThe sender places incoming messages in a buer, buer s.It tags the messages in its buer with successively larger integers(no gaps), starting from 1.The receiver assembles a buer, buer r , also containingmessages with tags starting from 1.As the buer gets lled in, the receiver can deliver theinitial messages in order.(Alternative modeling choice: eliminate the sender's buer in favor of ahandshake protocol with the user telling it when it can submit the nextmessage.)Other than the basic liveness condition described earlier, thisprotocol can tolerate a lot of unreliable behavior on the376part of the channel: loss, duplication and reordering.Note that only one direction of underlying channel is required,strictly speaking, although in this case, the sender never knows tostop sending any particular message.If we would like to eventually stop sending each message after it hasbeen delivered, need to also add an acknowledgement protocol in thereceiver-to-sender direction.The protocol can send lots of messages concurrently, but just to bespecic (and simple), we describe a \sequential" version of theprotocol, in which the sender waits to know that the previousmessage has been delivered to the receiver before starting to sendthe next version.Code: (see Figures A.1 and A.2).Correctness proof:Can give a high-level spec that is basically a queue, MQ, withsingle state component mqueue .A send-message action puts a message on the end and a receive-messageremoves it from the front.Same as our earlier channel spec.The liveness condition is then the same as we used before forindividual channels in our reliable network model { eventual deliveryof the rst message (easy spec as an IOA).The implementation consists of IOA's for the sender and receiver, butit is natural to use a more general model for theunderlying channels.However, I don't want to just use axioms for external behavior.To do a mapping proof,it is still convenient to have a state machine, even though thefairness condition needed isn't so easily specied using IOAfairness.State machine has as its state a set, send puts element into the set,can deliver a packet any number of times if it's in the set (nevergets removed from the set).377Interface:Input:send msg (m) m 2 Mreceive pkt rt (i) i a nonnegative integerOutput:send pkt tr (m i) m 2 M i a nonnegative integerState:buer , a nite queue of elements of M , initially empty, andinteger , a nonnegative integer, initially 1.Steps:send msg (m) m 2 MEect:add m to buer .send pkt tr (m i) m 2 M i a nonnegative integerPrecondition:m is rst on buer .i = integerEect:None.receive pkt rt(i) i a nonnegative integerEect:if i = integer thenremove rst element (if any) from buer integer := integer + 1]Partition:all send pkt tr actions are in one class.Figure A.1: Stenning Sender As378Interface:Input:receive pkt tr (m i) n 2 M i a nonnegative integerOutput:receive msg (m) m 2 Msend pkt rt (i) i a nonnegative integerState:buer , a nite queue of elements of M , initially empty, andinteger , a nonnegative integer, initially 0.Steps:receive msg (m) m 2 MPrecondition:m is rst on buer .Eect:remove rst element from buer .receive pkt tr (m i) m 2 M i a nonnegative integerEect:if i = integer + 1 thenadd m to buer integer := integer + 1]send pkt rt(i) i a nonnegative integerPrecondition:i = integerEect:None.Partition:all send pkt rt actionsall receive msg actionsFigure A.2: Stenning Receiver Ar379Liveness { i.e., the innite-send-innite-receive condition {is specied as an additional condition (a \liveness predicate").In order to prove that this works, it is useful to have some invariants:Lemma 1 The following are true about every reachable state of Stenning'sprotocol.1.