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

Suppose there is no decider. Then starting from a bivalent initialexecution, we construct a fair execution (no failures at all) in which successive prexes areall bivalent, thus violating the termination requirement.We work in a round-robin fashion: at each phase, we either let one specied process takea locally controlled step or else we deliver the rst message in some channel. Visiting allprocesses and all channels in the round robin order yields a fair execution (if a channel isempty, we can bypass it in the order).We have now reduced the proof to doing the following.

We need to consider one step ata time, where each step starts with a particular bivalent input-rst execution and we needto either21. let a particular process i take a turn, or2. deliver the oldest message in some channel.3531We must do this while keeping the result bivalent. We proceed by considering the possiblecases of the step at hand.Case 1: Deliver message m from j to i, where m is the rst message in the channel fromi to j in the state after . Consider the tree of all possible nite extensions of in whichm is delivered to i just at the end (in the interim, arbitrary other steps can occur). If anyof these \leaves" is bivalent, we are done with this stage.

So assume all are univalent. As inLoui-AbuAmara, assume without loss of generality that delivering the message immediatelyafter leads to a 0-valent state. Consider a nite extension of that contains a decision of1 this is possible because is bivalent (see Figure 25.4).αm delivered0−valent1Figure 25.4: the delivery of m leads to a 0-valent state.We now use this to get a conguration involving one step, such that if m is deliveredjust before the step the result is a 0-valent execution, whereas if it is delivered just afterthe step, the result is a 1-valent execution (see Figure 25.5). We show this must happen byconsidering cases as follows.m delivereds0−valentm delivered1−valentFigure 25.5: the delivery of m before step s leads to a 0-valent state, and the delivery of mafter step s leads to a 1-valent state.354If the extension leading to the decision of 1 does not contain a delivery of m, thendelivering m right at the end leads to a 1-valent state then since attaching it anywhere givesunivalence, there must be 2 consecutive positions along the chain where one gives 0-valenceand one gives 1-valence (see Figure 25.6).α1αm delivered0−valentm delivered0−valentm delivered1−valentm delivered1−valentm delivered0−valentm delivered1−valent1−valent1Figure 25.6: Left: the delivery of m does not appear in the extension to a 1-valent state.Right: m is delivered in the extension of .On the other hand, if this extension does contain a delivery event for m, then consider theplace where this delivery occurs.

Immediately after the delivery, we must have univalence,which for consistency with the later decision in this execution must be 1-valence. Then weuse the same argument between this position and the top.Now, if the intervening step (step s in Figure 25.5) involves some process other than i,then it is also possible to perform the same action after the delivery of m, and the resultingglobal state is the same after either order of these two events (see Figure 25.7).m deliveredss0−valentm delivered1−valentFigure 25.7: if s does not involve i, then performing s before or after m contradicts valency.But this is a contradiction, since one execution is supposed to be 0-valent and the other3551-valent.

So it must be that the intervening step involves process i.But then this yields a decider, a contradiction to the assumption.Case 2: Process i take a locally-controlled step.Essentially the same argument works in this case we only sketch it. Consider the tree ofnite extensions in which anything happens not including a locally-controlled step of i, andthen i does a locally-controlled step.

(Here we use the assumption that locally-controlledsteps are always possible.) Note that the tree can include message deliveries to i, but notlocally-controlled steps of i, except at the leaves.This time, we get a conguration involving one step, such that if i takes a locallycontrolled step just before this step, the result is a 0-valent execution, whereas if i takes itslocally-controlled step just after the step, the result is a 1-valent execution. Again, we getthis by cases.

If the extension doesn't contain a locally-controlled step of i, we can attach itat the end and proceed as in Case 1. If it does, then choose the rst such in the extensionand proceed as in Case 1. Then we complete the proof is as in Case 1, by showing thateither commutativity holds or a decider exists.25.2 Ben-Or Randomized Protocol for ConsensusFischer, Lynch and Paterson show that consensus is impossible in an asynchronous systemeven for simple stopping faults. However, this is only for deterministic algorithms. It turnsout that the problem can be solved in an asynchronous environment using randomization,with probability 1 of eventually terminating. In fact, an algorithm can even be designed totolerate stronger types of process faults | Byzantine faults, where processes can move toarbitrary states, and send arbitrary messages at any time.The algorithm uses a large number of processes relative to the number of faults beingtolerated, e.g., n 7f + 1.

(This can be reduced, but this version is easiest to see.) Thealgorithm proceeds as follows. Each process starts with its initial value in variable x. Thealgorithm works in asynchronous \phases", where each phase consists of two rounds. Eachprocess sends messages of the form rst (r v) and second (r v) where r is the phase numberand v is a value in the domain being considered.

The code is given in Figure 25.8 for binaryvalues. We assume for simplicity that the nodes continue performing this algorithm forever,even though they only decide once.25.2.1 CorrectnessValidity. If all the processes start with the same initial value v , then it is easy to see thatall nonfaulty processes decide on v in the rst phase: In the rst round of phase 1, all the356Initially, x is i's initial value.For each phase r do:Round 1:broadcast rst (r x)wait for (n ; f ) messages of the form rst (r )if at least (n ; 2f ) messages in this set have same value vthen x velse x nilRound 2:broadcast second (r x)wait for (n ; f ) messages of the form second (r )Let v be the value occurring most often (break ties arbitrarily),and let m be the number of occurrences of vif m (n ; 2f )then (DECIDE v x v )else if m (n ; 4f )then x velse x randomFigure 25.8: Randomized Consensus Algorithm for Asynchronous Network: code for processi.nonfaulty processes broadcast rst (1 v) and receive rst (1 v) messages from at least n ; 2fprocesses.

Then in round 2 of phase 1, all nonfaulty processes broadcast second (1 v) andagain receive at least n ; 2f second (1 v) messages.Agreement. We show that the nonfaulty processes cannot disagree. We will also see thatall nonfaulty processes terminate quickly once one process decides. Suppose that process idecides v at phase r. This can happen only if i receives at least n ; 2f second (r v) messagesfor a particular r and v, which guarantees that each other nonfaulty process j receives atleast n ; 4f second (r v) messages.

This is true since although there can be some dierencein which processes' messages are received by i and j , process j must receive messages fromat least n ; 3f of the n ; 2f senders of the second (r v) messages received by i. Amongthose senders, at least n ; 4f must be nonfaulty, so they send the same message to j as toi. A similar counting argument shows that v must be the value occurring most often in pj 'sset of messages (since n > 7f ).

Therefore, process j cannot decide on a dierent value atphase r. Moreover, j will set x v at phase r. Since this holds for all nonfaulty processesj , it follows (as in the argument for validity) that all nonfaulty processes that have not yetdecided will decide v in phase r + 1.357Termination. Now it remains to argue that the probability that someone eventually terminates is 1. So consider any phase r. We will argue that, regardless of what has happened atprior rounds, with probability at least 2;n (which is quite small, but nevertheless positive),all nonfaulty processes will end up with the same value of x at the end of round r. In thiscase, by the argument for agreement, all nonfaulty processes will decide by round r + 1.For this phase r, consider the rst time any nonfaulty process, say i, reaches the point ofhaving received at least n ; f rst (r ) messages.

Let M be this set of messages, and let vbe the majority value of the set (dene v arbitrarily if there is no majority value). We nowclaim that for any second (r w) message sent by a nonfaulty process, we must have w = vor w = nil .

To see that this is true, suppose w 6= nil . Now, if second (r w) is sent by anonfaulty process j , then j receives at least n ; 2f rst (r w) messages. Since (by counting)at least n ; 4f rst (r w) messages appear in M , and since n 7f + 1, this is a majority,and so we have w = v.Next, we claim that at any phase r, the only value that can be \forced upon" anynonfaulty process as its choice is v. To see this, note that for a process to be forced to choosew, the process must receive at least n ; 4f second (r w) messages.