Introduction to Distributed Algorithms - Solutions and Suggestions. Gerald Tel (Introduction to Distributed Algorithms - Solutions and Suggestions. Gerald Tel.pdf), страница 10

Action (1) makes theblack process white without making any other process black (a white neighbor could becomegray) and action (2) makes a gray process white without darkening any other process. Sothe pair formed by the numbers of black and gray processes decreases lexicographically withevery step and after less than N 2 steps a terminal configuration is reached. In a terminalconfiguration no two neighbors are in M , and every node not in M has a neighbor in M ,hence M is a maximal independent set.Project 17.10.

An outerplanar graph has a node of degree two or less; now re-read pages 538through 540, replacing “six” by “three” and “five” by “two”.Exercise 17.12. Let the cost of π = hp0 , . . . , pk i be the pair (p0 , k). Ordering is lexicographically, but to get length increase, paths of length N or longer are larger than paths oflength below N .Exercise 17.13. When a spanning tree is known, the size is computed by summation persubtree, i.e., each node assigns its count the sum of the counts of its children plus one.Construction of a spanning tree without a priory knowledge of the network size was solvedby Dolev [Dol93].Exercise 17.14.

The update algorithm can compute the longest upward path for each nodewith the following choice of c, f , and the order. Let cp = 0 for each process p, and letfpq (x) = x + 1 if p is the father of q and −∞ otherwise; the order is reversed, i.e., longerpaths are smaller than short ones.35Appendix B: Graphs and NetworksExercise B.1.

To prove the first part, select a node v0 ; because the graph is connected everynode has a finite distance to v0 . Sort the remaining nodes as v1 through vN −1 in increasingorder of distance, i.e., i > j ⇒ d(vi , v0 ) ≤ d(vj , v0 ). For each of the vi , i > 0, a shortest pathfrom vi to v0 exists; the higher-numbered endpoint of the first edge is vi ; hence the numberof edges is at least N − 1.To show the second part we demonstrate that an acyclic graph contains at least onenode with degree 1 or less; otherwise an infinite path without selfloops could be created,unavoidably hitting a node occuring earlier in the path and revealing a cycle.

Then the proofis completed by induction; an acyclic graph on one node has degree 0, and removing a degree0 or degree-1 node from an acyclic graph reduces the number of nodes, keeping the graphacyclic.Exercise B.2. Let G = (V, E) be an undirected graph. Assume G is bipartite; fix on aparticular coloring and consider a cycle.

As adjacent nodes in the cycle are also adjacent inG, they are colored differently, hence the cycle is of even length.Now assume G has no odd-length cycles. Select an arbitrary node v0 (or, if G is notconnected: select a node in each connected component) and color node v red if d(v0 , v) isodd and black if d(v0 , v) is even. Let v and v 0 be adjacent nodes, π be any path from v0 tov and π 0 any path from v 0 to v0 . The cycle formed by concatenating π, edge vv 0 , and π 0 haseven length, showing that the lengths of π and π 0 have different parity. In particular, d(v0 , v)and d(v0 , v 0 ) have different parity, and v and v 0 have different colors.Exercise B.3.

A ring of even length has no odd-length cycle and a tree has no cycle at all;use Exercise B.2. In the hypercube, consider a particular node labeling as in Definition B.12and color node v red if the number of 1’s in the label is even and black otherwise. As thelabels of adjacent nodes differ in exactly one bit, their parity is different.Exercise B.4. Theorem B.4 is Theorem 5.2 of Cormen et al. [CLR90]; I won’t bother tocopy the proof here.Exercise B.6. A clique on N nodes has (N − 1)! different labelings that are a sense ofdirection.

Select a node v0 and observe that the N − 1 different labels can bearranged inexactly (N − 1)! different ways on the edges incident to v0 .1. Each arrangement can be extended to a (unique) sense of direction as follows. Thearrangement defines Lv0 (w) for all w 6= v0 ; set L(w, v0 ) = N − Lv0 (w) and Lu (w) =Lv0 (w) − Lv0 (u) mod N for u, w 6= v0 .To show that L is a sense of direction, label node v0 with 0 and node w 6= v0 withLv0 (w); the obtained node labeling witnesses that L is an orientation.The (N − 1)! labelins are all different, because they already differ in their projection onv0 . Consequently, there are at least (N − 1)! different senses of direction.2. Each sense of direction L has a different projection on v0 ; indeed, Lw (v0 ) = N − Lv0 (w)and Lu (w) = Lv0 (w) − Lv0 (u) mod N can be shown by reasoning with a node labelingwitnessing that L is a sense of direction.

Consequently, there are at most (N − 1)!different senses of direction.36A hypercube of dimension n has n! different labelings that are a sense of direction. Selecta node v0 and observe that the n different labels can be arranged in exactly n! different wayson the edges incident to v0 .For edges e = (u, v) and f = (w, x), define e and f to be parallel iff d(u, w) = d(v, x)and d(u, x) = d(v, w). Reasoning with a witnessing node labeling it is shown that the labelsof e and f in a sense of direction are equal if and only if e and f are parallel.

Furthermore,for each edge f in the hypercube there is exactly one edge e incident to v0 such that e and fare parallel. This shows that, like it is the case for cliques, the entire labeling is defined bythe labeling of the edges of a single node.Exercise B.7. Assume (1). By the definition of an orientation there exists a labeling N ofthe nodes such that Lu (v) = N (v) − N (u).

Using induction on the path, it is easily shownthat Sum(P ) = N (vk ) − N (v0 ). As labels are from the set {1, .., N − 1}, Lu (v) 6= 0, and allnode labels are different. It now follows that v0 = vk if and only if Sum(P ) = 0.Assume (2). Pick an arbitrary node v0 , set N (v0 ) = 0 and for all u 6= v0 set N (u) = Lv0 (u).It remains to show that this node labeling satisfies the constraints in the definition of anorientation. That is, for all nodes u1 and u2 , Lu1 (u2 ) = N (u2 ) − N (u1 ). For u 6= v0 , noteN (v0 ) = 0 and N (u) = Lv0 (u) so Lv0 (u) = N (u) − N (v0 ). As P = v0 , u, v0 is closed,Sum(P ) = 0, hence Lu (v0 ) = −Lv0 (u) = N (v0 ) − N (u).

For u1 , u2 6= v0 , as P = v0 , u1 , u2 , v0is closed, Sum(P ) = 0 and hence Lu1 (u2 ) = −Lv0 (u1 )−Lu2 (v0 ) = (N (u1 )−N (v0 ))−(N (v0 )−N (u2 )) = N (u2 ) − N (u1 ).A discussion of the equivalence and similar results for the torus and hypercube are foundin [Tel91].37References[CLR90]Cormen, T. H., Leiserson, C. E., and Rivest, R. L. Introduction to Algorithms. McGraw-Hill/MIT Press, 1990 (1028 pp.).[DHS+ 94] Dijkhuizen, G. H., Herman, T., Siemelink, W. G., Tel, G., and Verweij,A. Developments in distributed algorithms.

Course notes, Dept Computer Science,Utrecht University, The Netherlands, 1994.[Dol93]Dolev, S. Optimal time self-stabilization in dynamic systems. In proc. Int.Workshop on Distributed Algorithms (Lausanne, 1993), A. Schiper (ed.), vol. 725of Lecture Notes in Computer Science, Springer-Verlag, pp. 160–173.[Len94]Lenstra, A. Factoring. In proc. 8th Int.

Workshop on Distributed Algorithms(Terschelling (NL), 1994), G. Tel and P. Vitányi (eds.), vol. 857 of Lecture Notesin Computer Science, Springer-Verlag, pp. 28–38.[Mat87]Mattern, F. Algorithms for distributed termination detection. Distributed Computing 2, 3 (1987), 161–175.[Mat89]Mattern, F. Virtual time and global states of distributed systems.

In proc. Parallel and Distributed Algorithms (1989), M. Cosnard et al. (eds.), Elsevier SciencePublishers, pp. 215–226.[Tel91]Tel, G. Network orientation. Tech. rep. RUU–CS–91–8, Dept Computer Science,Utrecht University, The Netherlands, 1991. Anon. ftp from ftp.cs.ruu.nl file/pub/RUU/CS/techreps/CS-1991/1991-08.ps.gz.[Tel94]Tel, G. Maximal matching stabilizes in quadratic time. Inf.

Proc. Lett. 49, 6(1994), 271–272.[Tel00]Tel, G. Introduction to Distributed Algorithms, 2nd edition. Cambridge University Press, 2000 (596 pp.).[WT94]Wezel, M. C. van and Tel, G. An assertional proof of Rana’s algorithm. Inf.Proc. Lett. 49, 5 (1994), 227–233.38.