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

This exercise is solved by an extensive, but elementary manipulation withaxioms and definitions. Let the commutative, associative, and idempotent operator ? on Xbe given and define a binary relation ≤? by x ≤? y ⇐⇒ (x ? y) = x.12We shall first establish (using the assumed properties of ?) that the relation ≤? is a partialorder on X, i.e., that this relation is transitive, antisymmetric and reflexive.1. Transitivity: Assume x ≤? y and y ≤? z; by definition of ≤? , (x?y) = x and (y?z) = y.Using these and associativity we find (x ? z) = (x ? y) ? z = x ? (y ? z) = x ? y = x, i.e.,x ≤? z.2. Antisymmetry: Assume x ≤? y and y ≤? x; by definition of ≤? , x ? y = x andy ? x = y.

Using these and commutativity we find x = y.3. Reflexivity: By idempotency, x ? x = x, i.e., x ≤? x.In a partial order (X, ≤), z is the infimum of x and y w.r.t. ≤ if z is a lower bound, and zis the largest lower bound, i.e., (1) z ≤ x and z ≤ y; and (2) every t with t ≤ x and t ≤ ysatisfies t ≤ z also. We continue to show that x ? y is the infimum of x and y w.r.t. ≤? ; letz = x ? y.1.

Lower bound: Expand z and use associativity, commutativity, associativity again,and idempotency to find z ? x = (x ? y) ? x = x ? (y ? x) = x ? (x ? y) = (x ? x) ? y =x ? y = z, i.e., z ≤? x.Expand z and use associativity and idempotency to find z ? y = (x ? y) ? y x ? (y ? y) =x ? y = z, i.e., z ≤? y.2. Smallest l.b.: Assume t ≤? x and t ≤? y; by definition, t ? x = t and t ? y = t.

Then,using these, z = x ? y, and associativity, we find t ? z = t ? (x ? y) = (t ? x) ? y = t ? y = t,i.e., t ≤? z.In fact, the partial order is completely determined by its infimum operator, i.e., it ispossible to demostrate that ≤? as defined above is the only partial order of which ? is theinfimum operator. This proof is left as a further exercise!Exercise 6.5. Consider the terminal configuration γ as in the proof of Theorem 6.16. It wasshown there that at least one process has decided; by Lemma 6.4 all other processes havesent, and by the algorithm the process itself has sent, so K = N .

Now F , the number of falserec bits, equals N − 2 and each process has either 0 or 1 of them; consequently, exactly twoprocesses have 0 false rec bits.Exercise 6.6. Each message exchanged in the echo algorithm contains a label (string) anda letter. The initiator is assigned label and every non-initiator computes its node labelupon receipt of the first message (from its father), by concatenating the label and the letterin the message.

When sending tokens, a process includes its node label, and the letter inthe message is chosen different for each neighbor. In this way the label of each node extendsthe label of its father by one letter, and the labels of the sons of one node are different. Tocompute the link labels, each node assigns to the link to the father the label and to allother links the label found in the message received through that link. If a message from theinitiator is received but the initiator is not the father, the node has a frond to the root andrelabels its father link with the label of the father (cf.

Definition 4.41).The labeling can be computed in O(D) time because it is not necessary that a nodewithhelds the message to its father until all other messages have been received (as in theEcho algorithm). In fact, as was pointed out by Erwin Kaspers, it is not necessary to send13messages to the father at all. When forwarding the message h tok, lu , a i to neighbor w, usets αuw to lu a, which is w’s label in case it becomes u’s son. When a message h tok, l, b i islater received from w, αuw is set to l.

The modified algorithm exchanges only 2E − (N − 1)messages, but is more difficult to terminate. Processes must wait indefinitely for the possiblereceipt of a message from every neighbor that has become a son.Exercise 6.7. The crucial step in the proof is that the first i messages received by q weresent in different send operations by p, and this is true even if some messages may get lost. Ifmessages can be duplicated, q may receive the same message more than once, so the first ireceive events may match less than i send events in p.Exercise 6.8.

According to Theorem 6.12, we must add a variable vp for process p, initializedto p’s input jp ; “send h tok i” and “receive h tok i” are replaced by “send h tok, vp i” and“receive h tok, v i ; vp := max(vp , v)”, respectively. Finally, upon deciding the output iswritten; here is the result:cons Dvar Recp [q]Sentpvp::::integer0..D0..Dinteger= the network diameter ;init 0, for each q ∈ Inp ;init 0 ;init jp (* the input *)begin if p is initiator thenbegin forall r ∈ Outp do send h tok, vp i to r ;Sentp := Sentp + 1end ;while minq Recp [q] < D dobegin receive h tok, v i from r; vp := max(vp , v) ;Recp [r] := Recp [r] + 1 ;if minq Recp [q] ≥ Sentp and Sentp < D thenbegin forall r ∈ Outp do send h tok, vp i to r ;Sentp := Sentp + 1endend ;outp := vpendExercise 6.9.

(a) As the algorithm counts the number of messages received, a duplicatedmessage may corrupt the count and cause a process to decide or send to its father too early.This can be remedied by administrating the received messages in a bit-array rather than in acount; when receiving form neighbor q, recp [q] is set to true. Sending to the father or decidingoccurs when all bits are true.(b) If a message h sets, Inc, N Inc i is received for the second time (by p), recp [q], Inc ⊆Incp and N Inc ⊆ N Incp hold already, so the message does not change the state of p andno new message is sent.

Consequently, the algorithm handles duplications correctly and nomodification is necessary.Exercise 6.10. In a complete bipartite network, if p is any process and q is any neighbor of p,then every process is a neighbor of p or a neighbor of q. The algorithm extends the sequential14polling algorithm (Algorithm 6.10) in the sense that the initiator polls its neighbors, and oneneighbor (q) polls all of its (q’s) neighbors.The initiator polls its neighbors, but uses a special token for exactly one of its neighbors(for example, the first). The polled processes respond as in Algorithm 6.10, except the processthat receives the special token: it polls all other neighbors before sending the token back tothe originator.Project 6.11. My conjecture is that the statement is true; if so, it demonstrates that senseof direction “helps” in hypercubes.Exercise 6.12.

In this picture the dotted lines arefronds and p is the root of the tree. The numberswritten at each node indicate the order in whichthe token visits the nodes.Observe that after the third step, when p has received the token from r, p forwards the token to s,while rules R1 and R2 would allow to send it backto r. This step is a violation of rule R3; of course,R3 must be violated somewhere to obtain a treethat is not DFS.p0, 3, 7, 10... . @@..@..@q .

. . .. . . . . . . . . . . .s4, 6.....r2, 8.1,.. 5, 9Exercise 6.13. The node labels are of course computed by a DFS traversal, where the tokencarries a counter that is used as the label and then incremented every time the token visits aprocess for the first time. After such a traversal (with any of the DFS algorithms presentedin Section 6.4) each process knows its father, and which of its neighbors are its sons. Thevalue ku in Definition 4.27 is found as the value of the token that u returns to its father. Noweach node can compute the link labels as in Definition 4.27 if it can obtain the node label ofeach of its neighbors.In the sequential algorithm (Algorithm 6.14) and the linear time variants (Algorithm 6.15and Algorithm 6.16/6.17) a node sends a message to each of its neighbors after receivingthe token for the first time. In this message the node label can be communicated to everyneighbor, which allows to perform the computation as argued above.In the linear message DFS algorithm (with neighbors knowledge, Algorithm 6.18) thelabels of neighbors can also be obtained, but at the expense of further increasing the bitcomplexity.

In addition to the list of all visited nodes, the token will contain the node label ofevery visited node. If node u has a frond to an ancestor w, then w and its label are containedin the token when u first receives it. If u has a frond to a descendant w, the token containsw and its label when the token returns to u after visiting the subtree containing w. In bothcases u obtains w’s label from the token before the end of the algorithm.Exercise 6.14. Each process sorts the list of names; the token contains an array of N bits,where bit i is set true if the process whose name has rank i is in the list.Exercise 6.15. Each message sent upwards in the tree contains the sum over the subtree;the sender can compute this sum because it knows its own input and has received messages(hence sums) from all its subtrees. In order to avoid an explicit distinction between messagesfrom sons (reporting subtree sums) and messages from the father and via fronds (not carryingany relevant information) we put the value 0 in every message not sent upward.

Assumingp’s input is given as jp , the program for the initiator becomes:15begin forall q ∈ Neighp do send h tok, 0 i to q ;while recp < #Neighp dobegin receive h tok, s i ; jp := jp + s ; recp := recp + 1 end ;Output: jpendand for non-initiators:begin receive h tok, s i from neighbor q ; father p := q ; recp := 1 ;forall q ∈ Neighp , q 6= father p do send h tok, 0 i to q ;while recp < #Neighp dobegin receive h tok, s i ; jp := jp + s ; recp := recp + 1 end ;send h tok, jp i to father pendNon-initiators ignore the value received in the first message; however, this value is not receivedfrom a son and it is always 0.Exercise 6.17.

In the longest message chain it is always the case that the receipt of miand the sending of mi+1 occur in the same process. Otherwise, the causal relation betweenthese events is the result of a causal chain containing at least one additional message, andthe message chain can be extended.The chain time complexity of Algorithm 6.8 is exactly N .First, consider a message chain in any computation. In the algorithm each process sendsto every neighbor, and these sends are not separated by receives in the same process; consequently, each message in the chain is sent by a different process.