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

After suciently many rounds, all the46inputs will propagate to all the participants (in the graph setting, this requires knowledge ofan upper bound on the diameter). Having propagated all the inputs, virtually any rule canbe used: in our case, the rule is \attack if there is no objection". Since all the participantsapply the same rule to the same set of input values, they will all decide identically.In a model with more uncertainty, in which messages may be lost, this simplistic algorithmfails. It turns out that this is not just a problem with this algorithm we shall prove thatthere is no algorithm that always solves this problem correctly.Before we go on to prove the impossibility result, we state the problem a bit morecarefully.

We consider the following model. Consider processes i, for 1 i n, arrangedin an undirected graph G. We assume that all processes start with initial binary values(encoded in their states). We use the same synchronous model we have been working withso far, except that, during the course of execution, any number of messages might be lost.The goal is to reach consensus (i.e., identical decisions) in a xed number, say r, of rounds.We represent the decision by a special value encoded in the processes' states at the end ofthe last round. (Alternatively, we can require that the decision value will be output usingspecial messages the dierence is simply one more round.)We impose two conditions on the decisions made by the processes as follows.Agreement: All processes decide on the same value.Validity: If all processes start with 0, then the decision value is 0 and if all processes startwith 1 and all messages are delivered, then the decision value is 1.The agreement requirement is natural: we would certainly like to be consistent.

Thevalidity requirement is one possible formalization of the natural idea that the value decidedupon should be \reasonable". For instance, the trivial protocol that always decides 0 is ruledout by the validity requirement. We comment that the validity condition above is quite weak:if even one message is lost, the protocol is allowed to decide on any value.

Nevertheless, itturns out that even this weak requirement is impossible to satisfy in any nontrivial graph(i.e., a graph with more than one node). To see this, it suces to consider the special caseof two nodes connected by one edge (cf. homework problem).We shall need the following standard denition.Denition 1 Let and be two executions. We say that is indistinguishable from with respect to a process i, denoted i , if in both and , i has the same initial stateand receives exactly the same messages at the same rounds.The basic fact for any distributed protocol, is that if i , then i behaves the same in and . This simple observation is the key in the proof of the following theorem.47p1p2rFigure 4.1: Pattern of message exchanges between p1 and p2Theorem 1 There is no algorithm that solves the coordinated attack problem on a graphwith two nodes connected by an edge.Proof: By contradiction.

Suppose a solution exists, say for r rounds. Without loss ofgenerality, we may assume that the algorithm always sends messages in both directions atevery round, since we can always send dummy messages. We shall now construct a series ofexecutions, such that each of them will be indistinguishable from its predecessor with respectto one of the processes, and hence all these executions must have the same decision value.Specically, let 1 be the execution that results when both processes 1 and 2 start withvalue 1, and all messages are delivered.

By validity, both must decide 1 at the end of 1.Now let 2 be the execution that is the same as 1, except that the last message from process1 to 2 is not delivered. Note that although process 2 may go to a dierent state at the lastround, 1 1 2, and therefore, process 1 decides 1 in 2. By agreement, process 2 must alsodecide 1 in 2. Next, let 3 be the same as 2 except that the last message from process 2to 1 is lost. Since 2 2 3, process 2 decides 1 in 3, and by agreement, so does process 1.Continuing in this way, by alternately removing messages, eventually we get down to anexecution in which both processes start with 1 and no messages are delivered. As before,both processes are forced to decide 1 in this case.But now consider the execution in which process 1 starts with 1 but process 2 starts with0, and no messages are delivered.

This execution is indistinguishable from with respectto process 1, and hence process 1 will still decide 1, and so will process 2, by agreement. Butthis execution is indistinguishable from the execution in which they both start with 0 withrestpect to process 2, in which validity requires that they both decide 0, a contradiction.Theorem 1 tells us, in simple words, that there is very little that we can do in distributednetworks if the communication may be faulty, and the correctness requirements are strict.This result is considered to reect a fundamental limitation of the power of distributed48networks.However, something close to this problem must be solved in real systems. Recall thedatabase commit problem.

There, we had even a stronger condition for validity, namely,if anyone starts with 0, then the decision value must be 0. How can we cope with theimpossibility indicated by Theorem 1? We must relax our requirements. One possible idea isto use randomization in the algorithm, and allow some probability of violating the agreementand/or validity condition. Another approach is to allow some chance of nontermination. Wewill return to nonterminating commit protocols in a lecture or two.4.1.2 Randomized ConsensusIn this section we discuss some properties of randomized protocols for consensus. We shallconsider, as above, processes in an arbitrary connected graph.

Our model will allow randomized processes, as for the MIS (Maximal Independent Set) problem.In this section we weaken the problem requirement, and we allow for some small probability of error. Consider a protocol that works in a xed number r of rounds. Our mainresults in this section VargheseL92], are bounds on the \liveness probability" that an algorithm can guarantee in terms of and r, that is, for the probability that all the participantsattack in the case where both start with 1 and all messages are delivered.We shall give an upper bound on the liveness probability. (Note that here an \upperbound" is a negative result: no algorithm will decide to attack in this case with too highprobability.) We shall also see an algorithm that (nearly) achieves this probability.Formal Modeling.

We must be careful about the probabilistic statements in this setting,since it is more complicated than for the MIS case. The complication is that the executionthat unfolds depends not only on the random choices, but also on the choices of whichmessages are lost. These are not random. Rather, we want to imagine they are under thecontrol of some \adversary", and we want to evaluate the algorithm by taking the worst caseover all adversaries.Formally, an adversary is (here) an arbitrary choice ofinitial values for all processes, andsubset of f(i j k) : (i j ) is an edge, and 1 k r is a round numberg.The latter represents which messages are delivered: (i j k) means that the message crossing (i j ) at round k gets through. Given any particular adversary, the random choices madeby the processes induce a probability distribution on the executions.

Using this probability49space, we can express the probability of events such as agreeing, etc. To emphasize this fact,we shall use the notation PrA for the probability function induced by a given adversary A.Let us now restate the generals problem in this probabilistic setting. We state it in termsof two given parameters, and L.Agreement: For every adversary A,PrA some process decides 0 and some process decides 1] Validity:1. If all processes start with 0, then 0 is the only possible decision value.2. If A is the adversary in which all processes start with 1 and all messages getthrough, then PrA all decide 1] L.We stress that we demand the rst validity requirement unconditionally | in the databasecontext, for example, one cannot tolerate any probability of error in this respect.Our goal is, given , a bound on the probability of disagreement, and r, a bound on thetime to termination, we would like to design an algorithm with the largest possible L.Example Protocol: (two processes).

We start with a description of a simple protocolfor two processes that will prove insightful in the sequel. The protocol proceeds in r roundsas follows.In the rst round, process 1 chooses an integer key , uniformly at random from the rangef1 : : : rg. The main idea of the algorithm is that this key will serve as a \threshold" for thenumber of rounds of communication that must be completed successfully, or otherwise theprocessors will resort to the default value, 0. Specically, at each round the processes sendmessages with the following contents.their initial values,(from process 1 only) the value of key , anda color, green or red.Intuitively, a message colored red signies that some message was lost in the past.

Moreprecisely, round 1 messages are colored green, and process i's round k message is coloredgreen provided that it has received all the messages at all previous rounds, and they wereall colored green otherwise, it is colored red.We complete the specication of the protocol by the following attack rule:50A process attacks exactly if it \knows" that at least one process started with 1,it \knows" the value of key , and it has received green messages in all the rstkey rounds.Let us make a small digression here to formally dene what does it mean for a processto \know" the value of some variable.Denition 2 A process i is said to know at time k the value of a variable v if either of thefollowing holds.v is a local variable of i, orby time k 0 k, i receives a message from a process that knows v at time k0 ; 1.The denition is simplied since we consider only variables whose values are set beforeany message is sent, and never changed afterwards.

It is straightforward to extend thedenition to the general case.Another way to view the \knowledge" of a process is to think of the execution graphdened as follows. The execution graph is a directed graph, with a node (i k) for each processi and for each round k, and a directed edge for each delivered message, i.e., ((i k) (i0 k + 1))is an edge i a message is sent from i to i0 at round k and is delivered by round k + 1. Withthis abstraction, Denition 2 says that a process i knows at time k everything about thenodes from which (i k) is reachable. Notice that in eect we assume that a node tells \all itknows" in every message.Analysis.