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

LetS be the k-neighborhood of p (S is a segment of length 2k + 1). Since R is c-symmetric,there must be at least one other segment in R which is order-equivalent to S let q be themidpoint of that segment. Now, by Lemma 1, p and q remain in equivalent states throughoutthe execution, up to the election point. We conclude that q also gets elected, a contradiction.31Now we can prove the lower bound.Theorem 4 All comparison-based leader election algorithms for rings of size n send !(n log n)messages before termination.Proof: DenepcnK = 1 + max k : n 2k + 1 n and 2k + 1 2 :Note that K cn4 .By Lemma 3 there are at least K active rounds. Consider the rth active round, where1 r K .

Since the round is active, there is some processor p that sends a message inround r. Let S be the (r ; 1)-neighborhood of p. Since R is c-symmetric, there are atpleast 2rcn;1 segments in R that are equivalent to S (provided n r ; 1). By Lemma 1,at the point just before the rth active round, the midpoints of all these segments are incorresponding states, so they all send messages.Thus, the total number of messages is at least0 4 1KXcn = ! @cn X1Ap rr=pn+1 2r ; 1 r= ncnp integral approximation of the sum= ! cn ln 4 ; ln n= !(n log n) :cnRemark : The paper by Attiya, Snir and Warmuth contains other related results aboutlimitations of computing power in synchronous rings.2.2 Leader Election in a General NetworkSo far, we considered only a very special kind of networks, namely rings.

We now turn toconsider more general networks, in the same synchronized model. We shall start with leaderelection.Let us rst state the problem in the general framework. Consider arbitrary, unknown,strongly connected network digraph G = (V E ). We assume that the nodes communicateonly over the directed edges.2 Again, nodes have UIDs, but the set of actual UIDs is unknown.The goal is, as before, to elect a leader.To solve the problem, we use a generalization of the idea in the LCR algorithm as follows.In the BFS example below we will remove this restriction and allow two-way communication even whenthe edges are 1-way.232Every node maintains a record of the maximum UID it has seen so far (initiallyits own). At each round, node propagates this maximum on all its outgoingedges.Clearly, the processor with the maximum UID is the only one that will keep its own UIDforever as the maximum.

But how does the processor with the maximum \know" that itis the maximum, so it can do an elected output? In LCR, it was enough that a processorreceived its own UID on an incoming link, but that was particular to the ring networktopology, and cannot work in general. One possible idea is to wait for suciently long time,until the process is guaranteed that it would have received any larger value, if one existed.It can be easily seen that this time is exactly the maximum distance from any node in thegraph to any other, i.e., the diameter. Hence, this strategy requires some built-in informationabout the graph.

Specically, every node must have an upper bound on the diameter.3We now specify the above algorithm formally. We describe process i.state (i) consists of components:own , of type UID, initially i's UIDmax-id, of type UID, initially i's UIDstatus , with values in funknown chosen reported g, initially unknownrounds , integer, initially 0.msgs (i): Send message m, a UID, to clockwise neighbor exactly if m is thecurrent value of max-id.Send leader to dummy node exactly if status = chosen .trans (i):Suppose new message from each neighbor j is m(j ).If status = chosen then status := reportedrounds := rounds + 1max-id := max(fmax-idg fm(j ) : j 2 in-nbrs(i)g)If rounds diam and max-id = own and status = unknown then status := chosenComplexity: it is straightforward to observe that the time complexity is diam rounds,and that the number of messages is diam jE j.It is possible to design a general algorithm for strongly connected digraphs that doesn't use this diameterinformation it is left as an exercise.3332.3 Breadth-First SearchThe next problem we consider is doing BFS in a network with the same assumptions as above.More precisely, suppose there is a distinguished source node i0.

A breadth-rst spanning treeof a graph is dened to have a parent pointer at each node, such that the parent of any nodeat distance d from i0 is a node at distance d ; 1 from i0. The distinguished node i0 has a nilpointer, i.e., i0 is a root. The goal in computing a BFS tree is that each node will eventuallyoutput the name of its parent in a breadth-rst spanning tree of the network, rooted at i0.The motivation for constructing such a tree comes from the desire to have a convenientcommunication structure, e.g., for a distributed network graph. The BFS tree minimizes themaximum communication time to the distinguished node.The basic idea for the algorithm is the same as for the sequential algorithm.At any point, there is some set of nodes that is \marked", initially just i0.

Othernodes get marked when they rst receive report messages. The rst round aftera node gets marked, it announces its parent to the outside world, and sends areport to all its outgoing neighbors, except for all the edges from which the reportmessage was received. Whenever an unmarked node receives a report , it marksitself, and chooses one node from which the report has come as its parent.Due to the synchrony, this algorithm produces a BFS tree, as can be proved by inductionon the number of rounds.Complexity: the time complexity diam rounds (actually, this could be rened a little, tothe maximum distance from i0 to any node). The number of messages is jE j | each edgetransmits a report message exactly once.2.3.1 ExtensionsThe BFS algorithm is very basic in distributed computing.

It can be augmented to executesome useful other tasks. Below, we list two of them. As mentioned earlier, we shall assumethat communication is bidirectional on all links (even though the graph we compute for mighthave directed edges).Message broadcast. Suppose that a processor has a message that it wants to communicate to all the processors in the network. The way to do it is to \piggyback" the message onthe report messages, when establishing a BFS tree.

Another possibility is to rst producea BFS tree, and then use it to broadcast. Notice that for this, the pointers go opposite to34the direction of the links. We can augment the algorithm by letting a node that discovers aparent communicate with it so it knows which are its children.Broadcast-convergecast. Sometimes it is desirable to collect information from through-out the network. For example, let us consider the problem in which each node has someinitial input value, and we wish to nd to global sum of the inputs.

This is easily (andeciently) done as follows. First, establish a BFS tree, which includes two-way pointers soparents know their children. Then starting from the leaves, \fan in" the results: each leafsends its value to its parent each parent waits until it gets the values from all its children,adds them (and its input value), and then sends the sum to its own parent.

When the rootdoes its sum, the nal answer is obtained. The complexity of this scheme is O(diam ) time(we can rene as before) the number of messages is jE j to establish the tree, and then anextra O(n) to establish the child pointers and fan in the results.We remark that funny things happen to the time when the broadcast-convergecast is runasynchronously. We will revisit this as well as the other algorithms later, when we studyasynchronous systems.356.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchSeptember 17, 1992Lecture 33.1 Shortest Paths: Unweighted and WeightedToday we continue studying synchronous protocols. We begin with a generalization of theBFS problem.

Suppose we want to nd a shortest paths from a distinguished node i0 2 V(which we sometimes refer to as the root), to each node in V . Now we require that eachnode should not only know its parent on a shortest path, but also the distance.If all edges are of equal weights, then a trivial modication of the simple BFS treeconstruction can be made to produce the distance information as well.

But what if there areweights assigned to edges?This problem arises naturally in communication networks, since in many cases we havesome associated cost, for instance, monetary cost, to traverse the link.Specically, for each edge (i j ), let weight (i j ) denote its weight. Assume that every node\knows" the weight of all its incident edges, i.e., the weight of an edge appears in specialvariables at both its endpoint nodes. As in the case of BFS, we are given a distinguishednode i0 and the goal is to have, at each node, the weighted distance from i0.

The way tosolve it is as follows.Each node keeps track of the best-dist it knows from i0. Initially, best-dist(i0) = 0and best-dist(j ) = 1 for j 6= i0. At each round, each node sends its best-dist to allits neighbors. Each recipient node i updates its best-dist by a \relaxation step",where it takes the minimum of its previous best-dist value, and of best-dist(j ) +weight (j i) for each incoming neighbor j .It can be proven that, eventually, the best-dist values will converge to the correct bestdistance values. The only subtle point is when this occurs.

It is no longer sucient to waitdiam time | see, for example, Figure 3.1. However, n ; 1 time units are sucient. In fact,the way to argue the correctness of the above algorithm (which is a variant of the well knownBellman-Ford algorithm), is by induction on the number of links in the best paths from i0.This seems to imply that a bound on the number of nodes must be known, but thisinformation can easily be computed.36root10011Figure 3.1: the correct shortest paths from the root stabilize only after 2 time units, even thoughall nodes are reachable in one step.3.2 Minimum Spanning TreeWe shall now modify our model slightly, and assume that the communication graph is undirected, i.e., if there is an edge between nodes i and j , then i and j can exchange messages inboth directions. The edges, as in the previous algorithm, are assumed to have weights whichare known at their endpoints.

We continue to assume that nodes have UIDs.Before we dene the problem, let us dene a few standard graph-theoretic notions. Aspanning tree for a graph G = (V E ) is a graph T = (V E 0 ), where E 0 E , such that T isconnected and acyclic if T is acyclic (but not necessarily connected), T is called a spanningforest. The weight of a graph is the sum of the weights of its edges.The Minimum Spanning Tree (MST) problem is to nd a spanning tree of minimalweight.

In the distributed setting, the output is a \marked" set of edges | each node willmark those edges adjacent to it that are in the MST. This problem arises naturally in thecontext of communication networks, since similarly to the BF tree, the MST is a convenientcommunication structure. The MST minimizes the cost of broadcast (i.e., when a nodewishes to communicate a message to all the nodes in the network).All known MST algorithms are based on the same simple theory.