Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 74
Текст из файла (страница 74)
Since at least one of thesemessages is from a nonfaulty process, it follows (from the previous claim) that w = v.Now, note that the value v is determined at the rst point where a nonfaulty process hasreceived at least n ; f rst (r ) messages. Thus, (by the last claim) the only forcible valuefor round r is determined at that point. But this point is before any nonfaulty process tossesa coin for round r, and hence these coin tosses are independent of the choice of forcible valuefor round r.
Therefore, with probability at least 2;n , all processes tossing coins will choosev, agreeing with all those that do not toss coins. This gives the claimed decision for roundr.The main interest in this result is that it shows a signicant dierence between therandomized and non-randomized models, in that the consensus problem can be solved in therandomized model. The algorithm is not practical, however, because its expected terminationtime is very high. We remark that cryptographic assumptions can be used to improve theprobability, but the algorithms and analysis are quite dicult. (See Feldman90].)25.3 Parliament of PaxosIn this section we'll see Lamport's recent consensus algorithm, for deterministic, asynchronous systems.
Its advantage is that in practice, it is very tolerant to faults of thefollowing types: node stopping and recovery lost, out-of-order, or duplicated messages linkfailure and recovery. However, it's a little hard to state exactly what fault-tolerance proper358ties it has, so instead we'll present the algorithm and then describe its properties informally.We remark that the protocol always satises agreement and validity. The only issue istermination { under what circumstances nonfaulty processes are guaranteed to terminate.The Protocol. All or some of the participating nodes keep trying to conduct ballots. Eachballot has an identier, which is a (timestamp index ) pair, where the timestamp needn't bea logical time, but can just be an increasing number at each node.
The originator of eachballot tries (if it doesn't fail) to (1) associate a value with the ballot, and (2) get the ballotaccepted by a majority of the nodes. If it succeeds in doing so, the originator decides on thevalue in the ballot and informs everyone else of the decision.The protocol proceeds in ve rounds as follows.1. The originator sends the identier (t i) to all processes (including itself). If a nodereceives (t i), it commits itself to voting \NO" in all ballots with identier smallerthan (t i) on which it has not yet voted.2.
Each process sends back to the originator of (t i) the set of all pairs ((t0 i0) v), indicating those ballots with identier smaller than (t i) on which the node has previouslyvoted \YES" it also encloses the nal values associated with those ballots. If theoriginator receives this information from a majority, it chooses as the nal value of theballot the value v associated with the largest (t0 i0) < (t i) that arrives in any of thesemessages.
If there is no such value reported by anyone in the majority, the originatorchooses its own initial value as the value of the ballot.3. The originator sends out ((t i) v), where v is the chosen value from round 2.4. Each process that hasn't already voted \NO" on ballot (t i) votes \YES" and sendsits vote back to the originator. If the originator receives \YES" votes from a majorityof the nodes, it decides on the value v.5. The originator sends out the decision value to all the nodes. Any node that receives italso decides.We rst claim that this protocol satises agreement and validity. Termination will needsome more discussion.Validity. Obvious, since a node can only decide on a value that is some node's initial value.359Agreement. We prove agreement by contradiction: suppose there is disagreement.
Let b bethe smallest ballot on which some process decides, and say that the associated value is v. Bythe protocol, some majority, say M , of the processes vote \YES" on b. We rst claim thatv is the only value that gets associated with any ballot strictly greater than b. For supposenot, and let b0 be the smallest ballot greater than b that has a dierent value, say v0 6= v.In order to x the value of ballot b0, the originator has to hear from a majority, say M 0,of the processes. M 0 must contain at least one process, say i, that is also in M , i.e., thatvotes \YES" on b.
Now, it cannot be the case that i sends its information (round 2) for b0before it votes \YES" (round 4) on b: for at the time it sends this information, it commitsitself to voting \NO" on all smaller ballots. Therefore, i votes \YES" on b before sendingits information for b0.
This in turn means that (b v) is included in the information i sendsfor b0. So the originator of b0 sees a \YES" for ballot b. By the choice of b0, the originatorcannot see any value other than v for any ballot between b and b0. So it must be the casethat the originator chooses v, a contradiction.Termination. Note that it is possible for two processes to keep starting ballots and preventeach other from nishing.
Termination can be guaranteed if there exists a \suciently longtime" during which there is only one originator trying to start ballots (in practice, processescould drop out if they see someone with a smaller index originating ballots, but this isproblematic in a purely asynchronous system), and during which time a majority of theprocesses and the intervening links all remain operative.The reason for the Paxos name is that the entire algorithm is couched in terms of actitious Greek parliament, in which legislators keep trying to pass bills. Probably thecutest part of the paper is the names of the legislators.3606.852J/18.437J Distributed AlgorithmsHandout 5September 10, 1992Homework Assignment 1Due: Thursday, September 17ReadingLamport-Lynch survey paper.Exercises1. Carry out careful inductive proofs of correctness for the LeLann-Chang-Roberts (LCR)algorithm outlined in class.2.
For the LCR algorithm,(a) Give a UID assignment for which !(n ) messages are sent.(b) Give a UID assignment for which only O(n) messages are sent.(c) Show that the average number of messages sent is O(n log n), where this averageis taken over all the possible orderings of the elements on the ring, each assumedto be equally likely.23. Write \code" for a state machine to express the Hirschberg-Sinclair algorithm, in thesame style as the code given in class for the LCR algorithm.4.
Show that the Frederickson-Lynch counterexample algorithm doesn't necessarily havethe desired O(n) message complexity if processors can wake up at dierent times.Briey describe a modication to the algorithm that would restore this bound.5. Prove the best lower bound you can for the number of rounds required, in the worstcase, to elect leader in a ring of size n. Be sure to state your assumptions carefully.3616.852J/18.437J Distributed AlgorithmsHandout 6September 17, 1992Homework Assignment 2Due: Thursday, September 24ReadingThe Byzantine generals problem, by Lamport, Shostak and Pease.Exercises1.
Prove the best lower bound you can for the number of rounds required, in the worstcase, to elect leader in a ring of size n. Be sure to state your assumptions carefully.2. Recall the proof of the lower bound on the number of messages for electing a reader ina synchronous ring. Prove that the bit-reversal ring described in class for n = 2k forany positive integer k, is -symmetric.123. Consider a synchronous bidirectional ring of unknown size n, in which processes haveUID's.
Give upper and lower bounds on the number of messages required for all theprocessors to compute n mod 2 (output is via a special message).4. Write pseudocode for the simple algorithm discussed in class, for determining shortestpaths from a single source i , in a weighted graph. Give an invariant assertion proofof correctness.05. Design an algorithm for electing a leader in an arbitrary strongly connected directedgraph network, assuming that the processes have UID's but that they have no knowledge of the size or shape of the network. Analyze its time and message complexity.6.
Prove the following lemma: If all the edges of a connected weighted graph have distinctweights, then the minimum spanning tree is unique.7. Consider the following variant of the generals problem. Assume that the network is acomplete graph of n > 2 participants, and that the system is deterministic (i.e., nonrandomized). The validity requirement is the same as described in class. However,suppose the agreement requirement is weakened to say that \if any general decides 1362then there are at least two that decide 1". That is, we want to rule out the case whereone general attacks alone.Is this problem solvable or unsolvable? Prove.3636.852J/18.437J Distributed AlgorithmsHandout 9September 24, 1992Homework Assignment 3Due: Thursday, October 1Exercises1.
Show that the generals problem (with link failures) is unsolvable in any nontrivialconnected graph.2. Consider the generals problem with link failures for two processes, in a setting whereeach message has an independent probability p of getting delivered successfully. (Assume that each process can send only one message per round.) For this setting, designan algorithm that guarantees termination, has \low probability" of disagreement (forany pair of inputs), and has \high probability" L of attacking in case both inputs are1 and there are no failures.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
