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

The action models the assumption of an upper limit on message delay, withoutconcern of how this bound is implemented; thus, the remaining packet lifetime is an idealized“mathematical” timer rather than a really existing clock device.Of course the situation can be considered where the network implements the bound usingphysical representations of a remaining packet lifetime for each process. A drift in theseclocks result in a changed actual bound on the delay: if the timers are supposed to implementa maximum of µ but suffer -bounded drift, the actual maximum packet lifetime is (1 + ) · µ.Exercise 3.8.

The invariants of the protocol are insensitive to the threshold in action Ep , ascan be seen from the proofs of Lemmas 3.10, 3.11, and 3.13; therefore the protocol remainscorrect.An advantage of the changed protocol is the shorter response time for the sender. A disadvantage is that more items may be inappropriately reported as lost.5Chapter 4: Routing AlgorithmsExercise 4.1. Consider a network that consists of a path of nodes v1 through vk , and a nodew connected to both v1 and vk , but its links go up and down repeatedly.

v1v2vk wConsider a packet m with destination w, and assume the link v1 w is down; the packet mustmove in the direction of vk , i.e., to the right. When the packet arrives in vk , the link to wgoes down but v1 w comes up; after adaptation of the routing tables the packet will move tov1 , i.e., to the left. When m arrives there, the link to w fails, but vk w is restored again, andwe are back in the situation we started with.In this example the network is always connected, yet m never reaches its destinationeven if the routing algorithm is “perfect” and instantaneously adapts tables to the currenttopology.Exercise 4.2. Yes, such a modification is possible; a message containing Dw is relayed tothose neighbors from which a h ys, w i message is received.

Unfortunately, neighboring processes may now be several rounds apart in the execution of the algorithm, i.e., a process mayreceive this message while already processing several pivots further. This implies that the Dwtable must be stored also during later rounds, in order to be able to reply to h ys, w i messagesappropriately. This causes the space complexity of the algorithm to become quadratic in N .The message complexity is reduced to quadratic, but the bit complexity remains the samebecause we unfortunately save only on small messages.Exercise 4.3.

To construct the example, let G be a part of the network, not containing v0 ,connected to v0 only through node u in G, and with the property that if Du [v0 ] improves byx while no mydist-messages are in transit in G, then K messages may be exchanged in G:'$'$v0uuv0uu&%u0u x uu@@xx &%@uvGG0Construct G0 by adding nodes u0 and v, and three edges uu0 , u0 v, and uv, each of weight x, andG0 is connected to v0 only via u0 .

When no messages are in transit in G0 , Du [v0 ] = Du0 [v0 ] + x,and assume in this situation Du0 [v0 ] improves by 2x (due to the receipt of a mydist-message).Consider the following scenario, in which u is informed about the improvement in two stepsby passing information via v.1. u0 sends an improved mydist-message to v and u.2. v receives the message, improves its estimate, and sends an improved mydist-messageto u.3.

u receives the message from v and improves its estimate by x, which causes K messagesto be exchanged in G.64. u receives the mydist-message from u0 and improves its estimate again by x, causinganother K messages to be exchanged in G.It is seen that when Du0 [v0 ] improves by 2x, more than 2K messages may be exchanged inG0 . By iterating the construction the number of nodes and edges grows linearly, while thenumber of messages grows exponentially; the resulting graph is as follows:uuuuuuuuu1@ 1@ 2@ 4@ 8@ 16@ 3232@@u 1@u 2 1@@u 4 2@@u 8 4@@u16 8@@u 32 16@v0A similar example can be given if the message delays are guaranteed to lie within a very smallrange.

The assumption of the Shortest Path measure is, however, necessary; in the MinimumHop measure the complexity of the algorithm is bounded by O(N · E) messages.Exercise 4.4. The following table gives the values of Du [v] and, between parenthesis, thevalue or possible values of N bu [v]; Recompute is non-deterministic w.r.t.

the selection ofa preferred neighbor if the minimal estimate occurs multiply. For each neighbor w of u,N disu [v, w] equals Dw [v].uvABCDEFA0 (loc)1 (B)4 (B/D)1 (D)2 (B/D)3 (B/D)B1 (A)0 (loc)3 (E)2 (A/E)1 (E)2 (E)C4 (F)3 (F)0 (loc)3 (F)2 (F)1 (F)D1 (A)2 (A/E)3 (E)0 (loc)1 (E)2 (E)E2 (B/D)1 (B)2 (F)1 (D)0 (loc)1 (F)F3 (E)2 (E)1 (C)2 (E)1 (E)0 (loc)Following Algorithm 4.9, node F sends upon receiving the h repair, A i message all entries of its distance table, i.e., messages: h mydist, A, 3 i, h mydist, B, 2 i, h mydist, C, 1 i,h mydist, D, 2 i, h mydist, E, 1 i, and h mydist, F, 0 i.Upon receipt of each of these six messages, Recompute is executed in A and leads to animprovement for destinations F and C, after which A sends messages h mydist, F, 1 i andh mydist, C, 2 i.Exercise 4.5. Let G be a ring of N processes, where the cost of each edge in clockwisekdirection is 1 and in anticlockwise direction the cost is k; then DG is approximately k+1N.

Aspanning tree of G is obtained by removing a single edge, and the distance between the twoseparated nodes is N − 1 in one direction but k · (N − 1) in the other direction; this is aboutk + 1 times DG .Exercise 4.6. Let the label of link uw (in node u) be αuw ; if αuw 6= lu , the link is used whena message with address αuw is generated in u. If αuw = lu but the label αuw + 1 does notoccur in u, the link is used when a message with address αuw + 1 is generated in u.

But ifαuw = lu and the label αuw + 1 also occurs in u, the link is never used.7This picture shows an example of an ILS where thisoccurs for the edge 12 on both sides; hence the edge12 is not used for traffic in neither direction. Thescheme is valid.A scheme not using edge uw is not optimal becausetraffic between u and w is sent over two or morehops while d(u, w) = 1.0102......... 221...1...200323x.u 1.. @ x2u...u@...

@ x3...u .u...u@......u .. u ..u. @ u...@......@uuuuu....u ...... u .. uu.u...y2... uu.u..y3.u.uy4uvExercise 4.7. Exploit Figure 4.16 to design a detour running through all nodes ofthe network. In this network, such a detour is made by messages from u to v. Thenodes marked xi send the message downthe tree via the dotted frond edges becauseyi+1 has a node label between xi+1 and v(both edges are labeled with the node label of the adjacent node).Exercise 4.8.

A DFS tree in a ring has depth N − 1; the ILS is as indicated here, and amessage from 0 to N − 2 travels via N − 2 hops (as does a message in the opposite direction).01N −32???123N −2N −1???N −2N −10 0 .N − 20 0 ....N −1. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 0Exercise 4.9. (1) Besides minimality, the only requirement on T is that it contains all ci ;consequently, every leaf of T is one of the ci (otherwise, a leaf could be removed, contradictingminimality).(2) Because a tree has N − 1 edges, the node degrees sum up to 2(N − 1), and leaveshave degree 1.

With m leaves, there are N − m nodes with degree at least 2, and thesedegrees sum up to 2N − m − 2; so the number of nodes with degree larger than 2 is at most2N − m − 2 − 2(N − m) = m − 2.8Chapter 5: Deadlock–free Packet SwitchingExercise 5.1. Consider the scenario in which each process generates a packet (for anothernode); this generation in empty nodes is allowed by the controller by definition. Now allbuffers are occupied but no packet is at its destination, hence the configuration is deadlocked.Dropping the requirement that every node should be able to send packets to another nodemakes a solution feasible. If all packets ever sent have the same destination v0 (so v0 cannotsend to another node), a single buffer per node, arranged as in the dest controller (Def.