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

The time complexity equals the maximal depth of the computation tree atthe moment termination occurs; this can be seen by quantifying the liveness argument inTheorem 8.5. As only processes are internal nodes, this depth is bounded by N . To showthat this is also a lower bound, observe that the time between termination and its detectionis N when the algorithm is applied to the Ring algorithm (Algorithm 6.2).Exercise 8.3. Construct the spanning tree in parallel with the basic computation anduse the tree algorithm (Algorithm 6.3) for the detection algorithm.

If the spanning tree iscompleted when the basic algorithm terminates, detection occurs within N time, but if thebasic algorithm terminates very fast this modification gives no improvement.Exercise 8.4. According to P0 , all pi with i > t are passive. So, if pj with j ≤ t is activated,P0 is not falsified because the state of all pi with i > t remains unchanged. If pj is activatedby pi with i > t, P0 is false already before the activation, hence it is not falsified.Exercise 8.5.

The basic computation circulates a token, starting from p0 , but in the oppositedirection. A process becomes passive after sending the token to its predecessor. A processholding the basic token performs local computations until its predecessor has forwarded thedetection token to it. In this way, the detection token is forwarded (N − 1) times betweenevery two steps of the basic token.Exercise 8.6. Action Rp becomes:Rp : { A message h mes, c i has arrived at p }begin receive h mes, c i ;if state p = activethen send h ret, c i to p0else begin statep := active ; credp := c endendExercise 8.7.

Observe that the process names are exclusively used by a process to recognizewhether it is the initiator of a token it receives; Knowledge of the ring size can be used alternatively. Tokens carry a hop counter, which is 1 for the first transmission, and incrementedevery time it is forwarded. When a token with hop count N is received (by a quiet process),termination is concluded.Exercise 8.8. This was done by Michiel van Wezel; see [WT94]. Now try your hands onMattern’s algorithm in [Mat87, Section 6.1].20Chapter 9: Anonymous NetworksExercise 9.1. Algorithm C repeats the subsequent execution of A and B until, according toB, ψ has been established. Explicit termination of A and B is necessary because the processesmust be able to continue (with B, or A, respectively) after termination.If A establishes ψ with probability P , the expected number of times A is executed by C is1/P ; if the complexity of A and B is known, this allows to compute the expected complexityof C.Exercise 9.2.

If the expected message complexity is K, the probability that the LV algorithm exchanges more than K/ messages is smaller than . We obtain an MC algorithm bysimulating the LV algorithm for at least K/, but at most a finite number of messages.Each process continues the execution until it has sent or received K/ messages. Indeed,with probability 1 − or higher, termination with postcondition ψ has occurred before thattime, and the number of overall communication actions is bounded (by N · K/), which showsthe new algorithm is Monte Carlo. (If K depends on network parameters such as the size,these parameters must be known.)Exercise 9.3.

A solution based on Algorithm 9.1 does not meet the time bound mentionedin the exercise, because the time complexity of the echo algorithm is linear. However, thelabeling procedure given in the solution to Exercise 6.6 assigns different names within thebounds.Exercise 9.4. Each process tries to send to every neighbor and to receive from every neighbor.When a process receives from some neighbor, it it becomes defeated and will thereafter onlyreceive messages. When a process succeeds to send to some neighbor, it keeps trying tosend to and receive from the other neighbors.

When a process has sent to every neighbor, itbecomes leader and will thereafter not receive any messages.At most one process becomes leader because if a process becomes leader, all its neighbors(i.e., all processes) are defeated and will not become leader. At most N − 1 processes becomedefeated because if this many processes are defeated there is no process that can send tothe last process. The algorithm terminates because only finitely many (viz., 21 N (N − 1))communications can occur; consider a terminal configuration. At least one process is notdefeated; if this process still wants to send, it can do so because all processes are ready toreceive.

Consequently, the process has sent to every neighbor and is leader.Exercise 9.5. Let the input of p be given as ap ; the following algorithm terminates afterexchanging at most N E messages, and in the terminal configuration, for every p: bp =maxq aq .bp := ap ; shout h val, bp i ;while true dobegin receive h val, b i ;if b > bp then begin bp := b ; shout h val, bp i end ;endExercise 9.6. (a) The processes execute the Tree algorithm (Algorithm 6.3), reducing theproblem to election between two processes, namely the two neighbors that send each a mes21sage.

These break symmetry by repeatedly exchanging a random bit: if the bits are equal,they continue; if they are different, the process that sent a 1 becomes leader.(b) No; this can be shown with a symmetry preserving argument like the one used toprove Theorem 9.5.Exercise 9.7. Both networks depicted in Figure 6.21 have diameter at most 2. Let anydeterministic algorithm be given; by using symmetry arguments as in the proof of Theorem 9.5it is shown that there is an execution in, say, the left network in which every process executesthe same steps. The same sequence of steps, executed by every process in the right network,constitutes an execution of the algorithm in that network. Consequently, the same answercan be found by the processes in the left and in the right network; but as the sizes of thesenetworks are different, the incorrect answer is found in at least one network.This argument is valid for process and for message terminating algorithms.

As the erroneous execution is finite, the argument shows that any probabilistic algorithm may err withpositive probability of error.Exercise 9.8. Assume N is composite, i.e., N = k · l for k, l > 1; divide the processes in kgroups of l each.

Call a coniguration symmetric if the sequence of l states found in one groupis the same for each group, i.e., si = si+l for each i. If γ is a symmetric configuration inwhich a communication event between pi and pi+1 is enabled, then the same event is enabledbetween pi+l and pi1 +l , between pi+2l and pi+1+2l , and so forth. These k events regard disjointpairs of processes (because l ≥ 2), hence the computation can continue with these k events inany order, after which a symmetric configuration is found again. In this way, either an infinitecomputation can be constructed, or a computation terminating in a symmetric configuration;the number of leaders in such a configuration is a multiple of k, hence not 1.Exercise 9.9.

The function f is non-constant (because there exist true as well as false valuedinputs), and hence is not computable by a process terminating algorihm if N is not known(Theorem 9.8).However, f can be computed by a process terminating algorithm. To this end, eachprocess sends its input to its successor, who will determine if the two input equal. If and onlyif mutual equality holds for all processes, f is true, so the problem of computing f reduces toevaluating the logical AND (Theorem 9.9).Exercise 9.10. The function g is cyclic, but non-constant, and hence is not computable bya process terminating algorihm (Theorem 9.8).To show that evaluation of g is also impossible by a message terminating algorithm,consider the rings R4 and R8 :7uPPP5u11PuBBBBu2 uR82BBBBuu11PPP 5Pu5u@2 u@@@u7R4@@@@u11722Assuming there exists a correct algorithm to compute g, there exists an execution, C4 say,of this algorithm on R4 that (message) terminates with result true.

Each process in R8 hasneighbors with the same inputs as the neighbors of its counterpart (the unique process inR4 with the same input). Consequently, there exists a computation of the algorithm on R8in which every process executes the same steps as its counterpart in R4 . In particular, thealgorithm (message) terminates with result true.Exercise 9.11.