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

This implies that the lengthof the chain is at most N .Second, consider an execution on processes p1 through pN where only p1 initiates thealgorithm and the first message received by pi+1 (for i > 1) is the one sent by pi . Thiscomputation contains a message chain of length N .(The time complexity of the algorithm is 2; because p1 sends a message to all processesupon initialization, all processes are guaranteed to send within one time unit from the start.Indeed, in the execution given above this single message is bypassed by a chain of N − 1messages.)16Chapter 7: Election AlgorithmsExercise 7.1.

Assume, to the contrary, that process l in network G becomes elected and itschange to the leader state is not preceded by any event in process p. Construct network G0 ,consisting of two copies of G, with one additional link between the two copies of process p;this is to ensure G0 is connected. In both copies of G0 the relative ordering of identities issimilar to the ordering of the identities in G. Because a comparison algorithm is assumed, thecomputation on G leading to the election of l can be replayed in the two parts of G0 , whichresults in a computation in which two processes become leader.Exercise 7.2.

Because h wakeup i messages are forwarded immediately by every process, allprocesses have started the tree algorithm withing D time units from the start of the wholealgorithm. It remains to show that the time complexity of the tree algorithm, including theflooding of the answer, is D; assume the tree algorithm is started at time t.Consider neighbors p and q in the tree; it can be shown by induction that process q sendsa message to p at the latest at time t+depth(Tqp ). (Indeed, the induction hypothesis allows toderive that by then q has received from all neighbors other then p.

If no message was receivedfrom p the “first” token by q is sent to p, otherwise a “flooding” token is sent.) Consequently,the latest possible time for p to decide is t + 1 + maxq∈Neigh depth(Tqp ), which is at mostpt + D (for p a leaf on the diameter path of the tree).PPmPExercise 7.3. For convenience, write H0 = 0j=1 1j = 0, so mi=0 Hi . Furtheri=1 Hi =Pi 1P1observe that Hi = j=1 j = Hm − i<j≤m j . NowPmi=0 Hi =====Pm i=0Hm −1jPi<j≤mPm1i<j≤m jPi=0Pm10≤i<j jPj=1mj=1 1P(m + 1)Hm −(m + 1)Hm −(m + 1)Hm −(m + 1)Hm − msee abovereverse summationsP1because0≤i<j j = 1 !!Exercise 7.4. This is an example of solving a summation by integration.

ByR Ndrawing+111rectangles of sizes i in a graph of the function f (x) = x it is easily seen that HN > x=1 dxx =ln(N + 1). The other bound is shown similarly.Exercise 7.5. As the token of the winner makes N hops, and each of the remaining N − 1processes initiates a token, which travels at least one hop, the number of messages is at least2N − 1. This number is achieved when each process except the one with smallest identityis followed in the ring by a process with smaller identity, i.e., the identities are “ordered”decreasingly in the message direction (mirror Figure 7.4).Exercise 7.6.

Instead of repeating the argument in the proof of Theorem 7.6, we give thefollowing informal argument.A non-initiator only forwards messages, so the sequence of non-initiators between two successive initiators simulates an asynchronous link between the two initiators.

It can thus be seenthat the number of messages sent by initiators is S · HS on the average.A message sent by an initiator may be forwarded for several hops by non-ititiators before be-17ing received by the next initiator; on the average, the number of links between two successiveinitiators is N/S. Consequently, the average complexity is N · HS .Exercise 7.7. We first construct the arrangements that yield long executions; if there aretwo processes (N = 21 ) with identities 1 and 2, the algorithm terminates in two (1 + 1)rounds. Given an arrangement of 2k processes with identities 1 through 2k for which thealgorithm takes k + 1 rounds, place one of the identities 2k + 1 through 2k+1 between eachof the processes in the given arrangement.

We obtain an arrangement of 2k+1 processes withidentities 1 through 2k+1 for which the algorithm uses k + 2 rounds.Assume the arrangement contains two local minima; if both minima and their neighborsinitiate, both minima survive the first round, so no leader is elected in the second round.Hence, to guarantee termination within two rounds the arrangement can have only one localminimum, which means that the identities are arranged as in Figure 7.4.

The algorithmterminates in one round if and only if there is a single initiator.Exercise 7.8. ECR = {(s1 , . . . , sk ) : 1 < i ≤ k ⇒ s1 < si }.Exercise 7.9. In the Chang-Roberts algorithm, process p compares a received identity q toits own, while in the extinction algorithm p compares q to the smallest identity p has seen sofar.A difference would occur if p receives an identity q smaller than its own, but larger thanan identity m received previously. However, this does not occur on the ring if communicationis fifo; p receiving m before q then implies that m is on the path from q to p in the ring,so m purges q’s token before it reaches p. In case of non-fifo communication the extinctionalgorithm may safe some messages over Chang-Roberts.Exercise 7.10. A connect message sent by a process at level 0 can be sent to a sleepingprocess.

Connect messages at higher levels are only sent to processes from which an acceptwas previously received, implying that the addressee is awake. A test message can also besent to a sleeping process.The other messages are sent via edges of the tree (initiate, report, changeroot) or in replyto another message (accept, reject), both implying that the addressee is awake.Exercise 7.11. Let the first node wake up at t0 , then the last one wakes up no later thant0 + N − 1.

By t0 + N all connect messages of level 0 have been received, and going to level 1depends only on propagation of initiate messages through the longest chains that are formed,and completes by t1 = t0 + 2N .Assume the last node reaches level l before time tl ≤ (5l − 3)N .

Each node sends lessthan N test messages, hence has determined its locally least outgoing edge by tl + 2N . Thepropagation of report, changeroot/connect, and initiate messages (for level l + 1) via MSTedges takes less than 3N time, hence by time tl+1 ≤ tl + 5N ≤ (5(l + 1) − 3)N , all nodes areat level l + 1.Exercise 7.12. The crux of the exercise is to show that Tarry’s traversal algorithm is anO(x) traversal in this case. Indeed, after 6x − 3 hops the token has visited a planar subgraphwith at least 3x − 1 edges, which implies that the visited subnetwork contains at least x + 1nodes. The election algorithm is now implied by Theorem 7.24.Exercise 7.13. Solution 1: Tarry’s traversal algorithm is an O(x) traversal algorithm for the18torus, because the degree of each node is bounded by 4.

Therefore, after 4x hops the tokenhas traversed at least 2x different edges, implying that x + 1 nodes were visited. The electionalgorithm is now implied by Theorem 7.24.Solution 2: By Theorem 7.21, election is possible in O(N log N + E) messages; for the torus,E = 2 · N , which implies an O(N log N ) bound.Exercise 7.14.

By Theorem 7.21, election is possible in O(N log N + E) messages; for thehypercube, E = 21 N log N , which implies an O(N log N ) bound.Exercise 7.15. By Theorem 7.21, election is possible in O(N log N + E) messages; the kbound on the node degrees implies that E ≤ 12 kN , showing that the GHS algorithm satisfiesthe requirements set in the exercise.The class of networks considered in this exercise is kN -traversable (using Tarry’s algorithm),but applying the KKM algorithm only gives an O(k.N log N ) algorithm.19Chapter 8: Termination DetectionExercise 8.1. Process p is active if the guard on an internal or send step is enabled, whichmeans, in Algorithm A.2, if(#{q : ¬recp [q]} ≤ 1 ∧ ¬sentp )∨ (#{q : ¬recp [q]} = 0 ∧ ¬decp ).All other states are passive.In Algorithm A.1 these passive states occur exactly when the process is waiting to executea receive statement.Exercise 8.2.