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

The n-Dimensional Hypercube: The initiator sends a message through its n linksin the first pulse. When receiving a message through link i, a process forwards the messagevia all links < i in the next pulse.It can be shown by induction on d that a node at distance d from th initiator receivesthe message exactly once, in pulse d, and via the highest dimension in which its node labeldiffers from the initiator. This shows that the message complexity is N − 1 and the numberof pulses is n.Exercise 12.7. When awaking, the processes initiate a wake-up procedure and then operateas in Section 12.2.1. As a result of the wake-up, the pulses in which processes start theelection may differ by D (the network diameter) but this is compensated for by waiting untilpulse p · (2D) before initiating a flood.Exercise 12.9.

The level of a node equals its distance to the initiator; if d(l, p) = fand q ∈ Neighp , then d(p, q) = 1 and the triangle inequality implies d(l, q) ≥ f − 1 andd(l, q) ≤ f + 1.27Chapter 14: Fault Tolerance in Asynchronous SystemsExercise 14.1. We leave the (quite trivial) correctness proofs of the algorithms as newexercises!If only termination and agreement are required: Each correct process immediately decideson 0. (This algorithm is trivial because no 1-decision is possible.)If only termination and non-triviality are required: Each process immediately decides onits input. (Agreement is not satisfied because different decisions can be taken.)If only agreement and non-triviality are required: Each process shouts its input, then waitsuntil d N 2+1 e messages with the same value have been received, and decides on this value. (Thisalgorithm does not decide in every correct process if insufficiently many processes shout thesame value.)Exercise 14.2.

We leave the (quite trivial) correctness proofs of the algorithms as newexercises!1. The even parity implies that the entire input can be reconstructed if N − 1 inputs areknown. Solution: Every process shouts its input and waits for the receipt of N − 1values (this includes the process’ own input). The N th value is chosen so as to makethe overall parity even. The process decides on the most frequent input (0 if there is adraw).2.

Solution: Processes r1 and r2 shout their input. A process decides on the first valuereceived.3. Solution: Each process shouts its input, awaits the receipt of N − 1 values, and decideson the most frequently received value.Can you generalize these algorithms to be t-crash robust for larger values of t?Exercise 14.3. As in the proof of Theorem 14.11, two sets of processes S and T can beformed such that the processes in each group decide independently of the other group. Ifone group can reach a decision in which there is a leader, an execution can be constructed inwhich two leaders are elected. If one group can reach a decision in which no leader is elected,an execution can be constructed in which all processes are correct, but no leader is elected.Exercise 14.4.

Choose disjoint subsets S and T of N − t processes and give all processesin S input 1 and the processes in T input 1 + 2. The processes in S can reach a decisionon their own; because all inputs in this group are 1, so are the outputs. Indeed, the samesequence of steps is applicable if all processes have input 1, in which case 1 is the only allowedoutput. Similarly, the processes in T decide on output 1 + 2 on their own.

The decisions ofS and T can be taken in the same run, contradicting the agreements requirement.Exercise 14.5. Write f (s, r) =12 (N− t + s − 1)(s − (N − t)) + r.Exercise 14.7. Call the components G1 through Gk . After determining that the decisionvector belongs to Gi , decide on the parity of i.Exercise 14.8. (1) Sometimes a leader is elected to coordinate a centralized algorithm.Execution of a small number of copies of this algorithm (e.g., in situations where election is28not achievable) may still be considerably more efficient than execution by all processes.(2) The decision vectors of [k, k]-election all have exactly k 1’s, which implies that the taskis disconnected (each node in GT is isolated).

The problem is non-trivial because a crashedprocess cannot decide 1; therefore, in each execution the algorithm must decide on a vectorwhere the 1’s are located in correct processes. Consequently, Theorem 14.15 applies.(3) Every process shouts its identity, awaits the receipt of N − t identities (including its own),and computes its rank r in the set of N − t identities. If r ≤ k + t then it decides 1, otherwiseit decides 0.Exercise 14.9.

(1) No, it doesn’t. The probability distribution on K defined by Pr[ K ≥k ] = 1/k satisfies limk→∞ Pr[ K ≥ k ] = 0, but yet E[ K ] is unbounded.(2) In all algorithms the probability distribution on the number of rounds K is geometric,i.e., there is a constant c < 1 such that Pr[ (K > k) ] ≤ c · Pr[ K ≥ k ], which implies thatE[ K ] ≤ (1 − c)−1 .Exercise 14.10. If all correct processes start round k, at least N − t processes shout in thatround, allowing every correct process to receive N − t messages and finish the round.Exercise 14.11.

(1) In the first round, less than N2−t processes vote for a value other thanv; this implies that every (correct) process receives a majority of votes for v. Hence in round2 only v-votes are submitted, implying that in round 3 all processes witness for v, and decideon v.(2) Assuming the processes with input v do not crash, more than N2−t processes vote for v inthe first round. It is possible that every (correct) process receives all v-votes, and less thanN −t2 votes for the other value.

Then in round 2 only v-votes are submitted, implying that inround 3 all (correct) processes witness for v, and decide on v.(3) Assuming the processes with input v do not crash, exactly N2−t processes vote for v in thefirst round. In the most favorable (for v) case, all correct processes receive N2−t v-votes andN −t2 votes for the other value. As can be seen from Algorithm 14.3, the value 1 is adoptedfor the next round in case of a draw.

Hence, a decision for v is possible in this case if v = 1.(Of course the choice for 1 in case of draw is arbitrary.)(4) An initial configurations is bivalent iff the number of 1’s, (#1), satisfiesN −tN +t≤ #1 <.22Exercise 14.12. (1) In the first round, more than N2+t correct processes vote for v; thisimplies that every correct process accepts a majority of v-votes in the first round, and hencechooses v. As in the proof of Lemma 14.31 it is shown that all correct processes choose vagain in all later rounds, implying that a v-decision will be taken.(2) As in point (1), in the first round all correct processes choose v in the first round, andvote for it in the second round.

Hence, in the second round each correct process accepts atleast N − 2t v-votes; as t < N/5 implies N − 2t > N2+t , is follows that in the second roundevery correct process decides on v.Exercise 14.13. Assume such a protocol exists; partition the processes in three groups, S,T , and U , each of size ≤ t, with the general in S.

Let γi be the initial configuration where29the general has input v.Because all processes in U can be faulty, γ0 →S∪T δ0 , where in δ0 all processes in S ∪ T havedecided on 0. Similarly, γ1 →S∪U δ1 , where in δ1 all processes in S ∪ U have decided on 1.Now assume the processes in S are all faulty and γ0 is the initial configuration. First theprocesses in S cooperate with the processes in T in such a way that all processes in S∪T decideon 0. Then the processes in S restore their state as in γ1 and cooperate with the processesin U in such a way that all processes in S ∪ U decide on 1. Now the correct processes in Sand U have decided differently, which contradicts the agreement.Exercise 14.14.

At most N initial messages are sent by a correct process, namely by thegeneral (if it is correct). Each correct process shouts at most one echo, counting for Nmessages in each correct process. Each correct process shouts at most two ready messages,counting for 2N messages in each correct process. The number of correct processes can be ashigh as N , resulting in the N · (3N + 1) bound.(Adapting the algorithm so as to suppress the second sending of ready messages by correctprocesses improves the complexity to N · (2N + 1).)30Chapter 15: Fault Tolerance in Synchronous SystemsExercise 15.1. Denote this number by Mt (N ); it is easily seen that M0 (N ) = N − 1.Further,Mt (N ) = (N − 1) + (N − 1) · Mt−1 (N − 1).(†)The first term is the initial transmission by the general,second term represents the N − 1Pt Qthei+1recursive calls.