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

We employ a new powerful idea here, namely randomization. Specically,in each iteration, each node i chooses an integer val (i) in the range f1 : : : B 4g at random,using the uniform distribution. (Here, we require the nodes to know B .) The upper boundB 4 was chosen to be suciently large so that with high probability, all nodes choose distinctvalues.

Having chosen these values, we dene I 0 to consist of all the nodes i such thatval (i) > val (j ) for all nodes j neighbors of i. This obviously yields an independent set, sincetwo neighbors cannot simultaneously be greater than each other.Formal Modeling. When we come to describe formally this synchronous algorithm, weencounter a problem: it doesn't quite t the model we have already dened. We need toaugment the model with some extra steps for the random choices. The option we adopt hereis to introduce a new \function", in addition to the message generation and transition functions, to represent the random choice steps.

Formally, we add an int (\internal transition")41component to the automaton description, where for each state s, int (s) is a probability distribution over the set of states. Each execution step will now proceed by rst using int topick a new (random) state, and then apply msgs and trans as usual.For the MIS algorithm, we rst outline the code in words. The algorithm works in phases,where each phase consists of three rounds.1. In the rst round of a phase, the nodes choose their respective val 's, and send them totheir neighbors. By the end of the rst round, when all the values have been received,the winners discover they are in I 0.2.

In the second round of a phase, the winners announce they are in I 0. By the end ofthis round, each node learns whether it has a neighbor in I 0.3. In the third round, each node with a neighbor in I 0 tells all its neighbors, and thenall the involved nodes: the winners, their neighbors, and the neighbors of winners'neighbors, remove the appropriate nodes and edges from the graph. Specically, thismeans the winners and their neighbors discontinue participation after this phase,andthe neighbors of neighbors will remove all the edges that are incident on the newlyremoved neighbors.Let us now describe the algorithm formally in our model.State:phase , integer, initially 1round : in f1 2 3g, initially 1val : in f1 : : :B 4 g,nbrs : set of vertices, initially the neighbors in the original graph Gawake : Boolean, initially truewinner : Boolean, initially falseneighbor : Boolean, initially falseint (i): (the global int is described by independent choices at all the nodes)if awake and round = 1 then val := rand (from uniform distribution)msgs (i): if awake = true andif round = 1:send val (i) to all nodes in nbrsif round = 2:42if winner = true thensend in-I to dummy nodesend winner to all nodes in nbrsif round = 3:if neighbor = true thensend neighbor to all nodes in nbrsBelow, we use the notation m:val to denote the particular component of the message.trans (i): if awake = true thencase:round = 1:if val > m(j ):val for all j 2 nbrs then winner := trueround = 2:if some winner message arrives then neighbor := trueround = 3:if winner _ neighbor then awake := falsenbrs := nbrs ; fj : a neighbor message arrives from j gendcaseround := (round mod 3) + 1Analysis.

Complete analysis can be found in the original paper by Luby. Here, we justsketch the proof.We rst state, without proof, a technical lemma which we need.Lemma 3 Let G = (V E ), and dene for an arbitrary node i 2 V ,X 1sum (i) =j 2nbrs (i) d(j )where d(j ) is the degree of j in G. Let I 0 be dened as in the algorithm above. ThenPr i 2 nbrs (I 0)] 41 min(sum (i) 1):Informally, the idea in proving Lemma 3 is that since the random choices made by thedierent nodes are independent identically distributed (iid) random variables, the probabilityof a given node i with d(i) neighbors to be a local maximum is approximately 1=d(i).

Sincewe are dealing with overlapping events, the inclusion-exclusion principle is used to obtainthe bound in the lemma.The next lemma is the main lemma in proving an upper bound on the expected numberof phases of the algorithm.43Lemma 4 Let G = (V E ). The expected number of edges removed from G in a single phaseof the algorithm is at least jE j=8.Proof: By the algorithm, all the edges with at least one endpoint in nbrs (I 0) are removed,and hence, the expected number of edges removed in a phase is at least1 X d(i) Pr i 2 nbrs (I 0)]2 i2VThis is since each vertex i has the given probability of having a neighbor in I 0 and ifthis event occurs, then it is certainly removed, and thereby it causes the deletion of d(i)edges.

The 21 is included to take account of possible overcounting, since an edge can havetwo endpoints that may cause its deletion,We now plug in the bound from Lemma 3:1 X d(i) min(sum (i) 1) :8 i2VBreaking this up according to which term of the \min" is less, this equals011 @ X d(i) sum (i) + X d(i)A8sum (i)1sum (i)<1Now expand the denition of sum (i) and write d(i) as sum of 1:01X d(i)X X A1@ X8 i:sum(i)<1 j2nbrs(i) d(j ) + i:sum (i)1 j2nbrs(i) 1Next, we make the sum over edges { for each edge, we have two endpoints for which theabove expression adds in the indicated terms, and so the preceding expression is equal to01!!1Bd(i) + d(j ) + Xd(i) + 1 + X (1 + 1)CBB XCC :@A8 i:sum(i)<1 d(j ) d(i)i:sum (i)<1 d(j )i:sum (i)1j :sum (j )<1j :sum (j )1sum (j )1Now each of the expressions within the summation terms is greater than 1, so the totalis at least 18 jE j.Using Lemma 4, it is straightforward to prove a bound on the expected number of phasesin Luby's algorithm.Theorem 5 The expected number of phases of the MIS algorithm is O(log n).Proof: By Lemma 4, 1=8 of the edges of the current graph are removed in each phase.Therefore, the total expected running time is O(log jE j) = O(log n).Remark.

Actually, a slightly stronger result holds: the number of phases in the MISalgorithm can be proven to be O(log n) with high probability.44Discussion. Randomization is a technique that seems frequently very useful in distributedalgorithms. It can be used to break symmetry, (e.g., it can be used for the leader electionproblem cf. homework problem). However, when designing randomized algorithms, onething that we must be careful about is that there is some possibility that things will gowrong. We have to make sure that such anomalies do not cause serious problems.

In MISalgorithms, for example, probabilistic anomalies may result in outputting a set which is notindependent, or not maximal. Fortunately, Luby's algorithm always produces an MIS. Theperformance of the algorithm, however, depends crucially on the random choices | it cantake more rounds if we are unlucky and \bad" choices are made. This is generally consideredto be acceptable for randomized algorithms. Even so, there is something worse here | it ispossible to have equal choices made repeatedly for neighbors, which means that there is apossibility (which occurs with zero probability) that the algorithm never terminates. Thisis less acceptable.456.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchSeptember 22, 1992Lecture 4Our next topic is the major example we shall study in the synchronous model, namely,consensus algorithms.

We shall spend some 2-3 lectures on this subject. The consensusproblem is a basic problem for distributed networks which is of interest in various applications. In studying this problem, we extend our model to include a new source of uncertainty:failures of communication links and processors.4.1 Link Failures4.1.1 The Coordinated Attack ProblemThe problem we will describe now is an abstraction of a common problem arising in distributed database applications.

Informally, the problem is that at the end of processinga given database transaction, all the participants are supposed to agree about whether tocommit (i.e., accept the results of) the transaction or to abort it. We assume that the participants can have dierent \opinions" initially, as to whether to commit or abort, e.g., dueto local problems in their part of the computation.Let us state the problem more precisely, cast in terms of generals the abstraction is dueto Gray.Several (sometimes only two) generals are planning to attack (from dierentdirections) against a common objective.

It is known that the only way for theattack to succeed, is if all the generals attack. If only some of the generalsattack, their armies will be destroyed. There may be some reasons why one ofthe generals cannot attack { e.g., insucient supplies. The generals are located indierent places, and can communicate only via messengers. However, messengerscan be caught, and their messages may be lost en route.Notice that if messages are guaranteed to arrive at their destinations, then all the generalscould send messengers to all the others, saying if they are willing to attack (in our previousterminology, all the nodes will broadcast their inputs).