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

5.8),suffices.Exercise 5.2. Consider the scenario in which u1 , u2 , w1 , and w2 concurrently generatea packet for v; this is allowed when the buffers for destination v are empty and results indeadlock.Exercise 5.3. The buffers of node u are bu [0] .

. . bu [k], like for the hops-so-far scheme, buthere an edge bu [i]bw [j] exists in the buffer graph if uw ∈ E and i − 1 = j. A packet p for v,generated in u, is placed in buffer f b(p) = bu [k], where k is the length of the used path fromu to v. If packet p in buffer bu [i] must be forwarded to node w, it must be placed in buffernb(p, bu [i]) = bw [i − 1] because from node w the packet has only i − 1 hops to go to v.In this buffer graph, the class of buffer bu [i] is k − i.

It will usually not be necessary toinclude the hop counter. To initialize it properly, the source of a packet with destination vmust know the hop distance to v, knowledge which will usually be taken from routing tablesat the source. The intermediate nodes also find the hop distance to v in their routing tables,so it is not necessary to include this information in the packet.Exercise 5.4. Let P = hu0 , u1 , . . . , ul i be the path for packet p and consider the sequenceof buffers obtained by b0 = f b(p) and bj+1 = nb(p, bj ). We must show that this sequencedefines a path in the buffer graph, i.e., after reaching the highest buffer index, B, no furtherincrement of the index is required.This is not hard to show but some subtlety is involved because the embedding of P in thecover may skip some of the orientations (i.e., Pi is empty for some i), while the buffer indexgrows at most one in every hop.

We first make explicit to what level of the cover each edgein P belongs: choose 1 = c0 ≤ c1 ≤ c2 . . . ≤ cl ≤ B such that uj−1 uj ∈ E~cj . Finally, let ij bethe buffer index of bj , i.e., bj = buj [ij ]; we show by induction that ij ≤ cj .Case j = 0: Because f b(p) = bu0 [1], i0 = 1, and by definition c0 = 1, hence i0 ≤ c0 .Case j + 1: The induction hypothesis states ij ≤ cj . By the definition of nb, ij+1 ≤ ij + 1so if ij < cj then ij+1 ≤ cj ≤ cj+1 and we are done.

If uj uj+1 ∈ E~ij then ij+1 = ij andwe are also done because ij ≤ cj ≤ cj+1 .The remaining case is where ij = cj and uj uj+1 6∈ E~ij ; this implies that ij+1 = ij + 1 =cj + 1. However, cj+1 > cj can be concluded in this case: because uj uj+1 6∈ E~cj , wehave cj+1 6= cj , hence cj ≤ cj+1 implies cj+1 > cj .Thus, the buffer index in node uj is at most the level of edge uj−1 uj in the embedding of Pin the cover, hence remains bounded by B.Project 5.5. We consider the Hypercube with the standard node labeling as in Definition B.12, i.e., the name of a node is a string of bits. The distance from u to v is the number9of positions i with ui 6= vi and an optimal path is obtained by reversing the differing bits inany order.Now adopt the following routing algorithm.

In the first phase, reverse the bits that are1 in u and 0 in v (in any order), then reverse the bits that are 0 in u and 1 in v. Thus, thenumber of 1-bits decreases in the first phase and increases in the second phase. All obtainedpaths are covered by the acyclic orientation cover HC0 , HC1 , where in HC0 all edges aredirected towards the node with the smaller number of 1’s and in HC1 the other way. Thisshows that deadlock free packet switching is possible with only two buffers per node.Shortest paths that are all emulated in the cover described here cannot be encoded inan interval labeling scheme.

In fact, Flammini demonstrated that the minimal number ofintervals√needed globally to represent shortestpaths covered by HC0 , HC1 is lower bounded√by Θ(N N ), which means that at least N / log N intervals per link (average) are needed.On the other hand, the cover described above is not the only cover of size two that emulatesa shortest path between every two nodes. Whether shortest paths emulated by another covercan be encoded in an interval labeling scheme is unknown.Exercise 5.6. We start to prove the correctness of BC.

First, if u is empty, fu = B henceB > k implies k − fu < 0, so the acceptance of every packet is allowed.To show deadlock-freedom of BC, assume γ is a deadlocked configuration and obtain δas in the proof of Theorem 5.17. Let p be a packet in δ that has traveled a maximal numberof hops, i.e., the value of tp is the highest of all packets in δ, and let p reside in u. Node u isnot p’s destination, so let w be the node to which p must be forwarded; as this is move is notallowed there is a packet in w (an empty node accepts every packet).

Choose q as the mostrecently accepted one of the packets in w and let fw0 be the number of free buffers in w justbefore acceptance of q; we find fw0 ≤ fw + 1. The acceptance of q implies tq > k − fw0 but therefusal of p implies tp + 1 ≤ k − fw . Consequently,tq > k − fw0 ≥ k − (fw + 1) ≥ tp ,contradicting the choice of p.As expected, the correctnessP of BS is a little bit more intricate. Again, an empty node accepts every packet because jt=0 it − B + k < 0; this shows that generation in (and forwardingto) empty nodes is allowed and we use it in the proof below.Again, assume a deadlocked configuration γ, and obtain δ as usual; choose p a packet inγ with maximal value of tp , let u be the node where p resides and w be the node to which pmust be forwarded. Choose q the packet in w that maximizes tq ; this choice implies it = 0for t > tq . Let r be the most recently accepted packet in w, and ~i and ~i0 the state vector ofw in δ, and just before accepting r, respectively.(1) The acceptance of r implies∀j, tr ≤ j ≤ k : j >jXi0t − B + k.t=0(2) The choice of r implies that it ≤ i0t for all t 6= ts and itr ≤ i0tr + 1, so we find∀j, ts ≤ j ≤ k : j >jXt=010it − B + k − 1.(3) In particular, with j = tq :tq >tqXit − B + k − 1.t=0(4) Now use that p is not accepted by w, i.e.,∃j0 , tp + 1 ≤ j0 ≤ k : j0 ≤j0Xit − B + k.t=0(5) This gives the inequalitytp <≤≤≤=≤tp + 1j0Pj0it − B + kPt=0kit − B + kPtt=0qt=0 it − B + ktq ,as chosen in (4)from (4)because it ≥ 0because it = 0 for t > tqsee (3)which contradicts the choice of p.Exercise 5.7.

Assume the acceptance of packet p by node u is allowed by BC; that is,tp > k − fu . As the path length is bounded by k, sp ≤ k − tp , i.e., sp < k − (k − fu ) = fu ;consequently the move is allowed by FC.11Chapter 6: Wave and Traversal AlgorithmsExercise 6.1. The crux of this exercise lies in the causal dependency between receive andsend in systems with synchronous message passing; a dependency that is enforced withoutpassing a message from the receiver to the sender.

Consider a system with two processes pand q; p may broadcast a message with feedback by sending it to q and deciding; completionof the send operation implies that q has received the message when p decides. On the otherhand, it will be clear that p cannot compute the infimum by only sending a message (i.e.,without receiving from q).The strength of the wave algorithm concept lies in the equivalence of causal chains andmessage chains under asynchronous communications. Hence, the causal dependency requiredfor wave algorithms implies the existence of message chains leading to a decide event andallows infimum computations.Wave algorithms for synchronous communications can be defined in two ways.

First,one may require a causal relation between each process and a decide event; in this case, thedefinition is too weak to allow infimum computation with waves, as is seen from the aboveexample. Second, one may require a message chain from each process to a decide event; inthis case, the definition is too strong to conclude that each PIF algorithm satisfies it, as isalso seen from the example. In either case, however, we lack the full strength of the waveconcept for asynchronous communications.Exercise 6.2. The proof assumes it is possible to choose jq0 such that J ≤ jq0 is not satisfied,i.e., that J is not a bottom.Let X be an order with bottom ⊥. If p has seen a collection of inputs whose infimum is⊥, a decision on ⊥ can safely be made because it follows that ⊥ is the correct output.

Nowconsider the following algorithm. Process p receives the inputs of its neighbors and verifieswhether their infimum is ⊥; if so, p decides on ⊥, otherwise a wave algorithm is started and pdecides on its outcome. This algorithm correctly computes the infimum, but does not satisfythe dependency requirement of wave algorithms.Exercise 6.3. The required orders on the natural numbers are:(1) Define a ≤ b as a divides b.(2) Define a ≤ b as b divides a.The first order has bottom 1, the second has bottom 0.The required orders on the subsets are:(1) Define a ≤ b as a is a subset of b.(2) Define a ≤ b as b is a subset of a.The first order has bottom ∅, the second has bottom U .The given solutions are unique; the proof of the Infimum Theorem (see Solution 6.4)reveals that the order ≤? whose infimum function is ? is defined bya ≤? b ≡ (a ? b) = a.Exercise 6.4.