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

The recursion is solved by Mt = i=0 j=1 (N − j).Exercise 15.2. If the decision value is 0 while the general is correct, the general’s input is0 and the discussion in Lemma 15.6 applies. No correct process p initiates or supports anycorrect process, hence the messages sent by p are for supporting a faulty process q; so p shoutsat most t times, which means sending (N − 1).t messages.If the general is faulty, at most L − 1 = t correct processes can initiate without enforcing a1-decision.

Correct process p shouts at most 1 h bm, 1 i message, at most t h bm, q i messagesfor faulty q, and at most t h bm, r i messages for correct r; this means sending at most(N − 1)(2t + 1) messages.Exercise 15.3. The faulty processes can send any number of messages, making the totalnumber unbounded; this is why we usually count the number of messages sent by correctprocesses only. Faulty g, p1 , p2 could conspire to send h val, v i : g : p1 : p2 for many values vto correct p to trap p into sending many messages. Therefore a message that repeats anothermessage’s sequence of signatures is declared invalid.Then, a correct general sends at most N − 1 messages in pulse 1, and for each sequenceg : p2 : .

. . : pi at most N − i messages are sent inPpulseQi by a process (pi ). Thus the numberiof messages sent by correct processes is at most t+1i=1j=1 (N − j).Exercise 15.4. Let p and q be correct; the first and second value accepted by p or q areforwarded, and also accepted by the other. So we let them both receive a third value fromfaulty processes, which is not received by the other:gstpq.. Round 1 ..

Round 2 ........HH.. AJ....@H.. AJ@ Hj.Ha ..*b ..AJ@.... HH.HAJ @ b ...HHR . @ja ..AJ......*AJ......cdJ . A ^....H*..AH...HHHAAUd .. jc .........Round 3@*@ @@Rb@@ @@aR@@....g is faulty.....s is faulty.....t is faulty....... Wp = {c, d, b}..... Wq = {d, c, a}..Observe that p and q forward the value c, and d, respectively, in round 2 and that they forwardin round 3 their second received value, namely d, and c, respectively. The third received value(b and a, respectively) is not forwarded in the next round.Exercise 15.5. The processes achieve interactive consistency on the vector of inputs; thename of p will be the rank of xp in this vector.Byzantine processes may refuse to participate, but then their default values are assumedto have the higher ranks in the list. They may also cheat by submitting other values than31their input, for example, the name of a correct process.

Then this name appears multiplyin the list and the correct process decides on the smallest i for which (in the sorted vector)V [i] = xp . Because all correct processes decide on the same vector and this decision vectorcontains the input of each correct process (by dependence), the decisions of correct processesare different and in the range 1 . . . N .Exercise 15.6. Process q receives signed messages M1 and M2 from p, i.e., the triples(M1 , r1 , s1 ) and (M2 , r2 , s2 ), where ri = g ai mod P and si = (M − d ri )a−1i mod (P − 1).Reuse of a, i.e., a1 = a2 is detected by observing that r1 = r2 in this case.

Subtracting s2 froms1 eliminates the unknown term d ri , as s1 −s2 = (M1 −M2 )a−1 , i.e., a = (M1 −M2 ) (s1 −s2 )−1(mod ()P − 1). Next we find d = (M1 − a s1 ) r−1 .Exercise 15.7. In rings without zero-divisors, i.e., the axiom a.b = 0 ⇒ a = 0∨b = 0 applies,a square is the square of at most two elements. Indeed, x2 = z 2 reads (x − z)(x + z) = 0 andhence, by the quoted axiom, x − z = 0 or x + z = 0, i.e., z = x or z = −x.

In particular, if p isa prime number, Zp is free of zero-divisors, and x2 = y 2 (mod p) implies y = ±x (mod p).Now let n = p.q be a composit; the ring Zn has zero-divisors because a.b = 0 holds if pdivides a and q divides b, or vice versa. Each square can be the square of up to four numbers;if y = x2 , then also y = zi2 forz1z2z3z4s.t.s.t.s.t.s.t.z1z2z3z4=x=x= −x= −x(mod(mod(mod(modp)p)p)p)andandandandz1z2z3z4=y= −y=y= −y(mod(mod(mod(modq)q)q)q)The four numbers form two pairs of opposites: z1 = −z4 and z2 = −z3 and possessing ziand zj such that zi = ±zj is useless. However, if we possess zi and zj from different pairs,compute a = zi + zj and b = zi − zj and observe that neither a nor b equals 0, while a.b = 0.Hence each of a and b is divided by one of p and q, so gcd(a, n) is a non-trivial factor of n.The square-root box can be used to produce such a pair.

Select a random number x anduse the box to produce a square root z of y = x2 . Because x was selected randomly, there isa probability of 21 that x and y are from different pairs, revealing the factors of n.(The main work in modern factoring methods is spent in finding a non-trivial pair ofnumbers with the same square [Len94].)Exercise 15.8. The clock Cq has ρ-bounded drift, meaning (Eq. 15.1) that its advance inthe real time span t1 –t2 (where t2 ≥ t1 ) differs at most a factor 1 + ρ from t2 − t1 , i.e.,(t2 − t1 )(1 + ρ)−1 ≤ Cq (t2 ) − Cq (t1 ) ≤ (t2 − t1 )(1 + ρ).This implies that the amount of real time in which the clock advances from T1 to T2 (whereT2 ≥ T1 ) differs at most a factor 1 + ρ from T2 − T1 , i.e.,(T2 − T1 )(1 + ρ)−1 ≤ cq (T2 ) − cq (T1 ) ≤ (T2 − T1 )(1 + ρ).Using only the second inequality we find, for any T, T 0 :| cq (T ) − cq (T 0 ) | ≤ (1 + ρ).| T − T 0 |.32Consequently, for T = Cp (t) we have| cq (T ) − cp (T ) | = | cq (Cp (t)) − cq (Cq (t)) | because Cp (T ) = t = cq (Cq (t))≤ (1 + ρ) .

| Cp (t) − Cq (t) | by the bounded drift of cq≤ (1 + ρ) . δas Cp , Cq are δ − synchronizedat real time t.Exercise 15.9. Process p asks the server for the time, the server replies immediately witha h time, T i message, and p measures the time I between sending the request and receivingthe reply. As the delay of the h time, T i message was at least I − δmax (this is because atmost δmax of the I time interval was used by the request message) and at most δmax , it differsat most δmax − I/2 from 21 I.

So, p sets its clock to T + 12 I , achieving a δmax − I/2 precision;if is smaller than δmax − I/2, the request is repeated.The probability that the delay of the request (or response) message exceeds δmax − is1 − F (δmax − ), so the probability that both delays exceed δmax − is [1 − F (δmax − )]2 .This implies that the expected number of trials is at most [1 − F (δmax − )]−2 , hence theexpected number of messages is at most 2.[1 − F (δmax − )]−2 and the expected time is atmost 2δmax .[1 − F (δmax − )]−2 .Exercise 15.10. No, certainly not. Assume N − t processes submit the value x, and inaddition p receives the values x − δ and x + δ.

Although at least one of these is erroneous(they differ by more than δ), neither of them is rejected because both have N − t submissionsthat differ δ from it. This lower bounds width(Ap ) to 2δ.33Chapter 17: StabilizationExercise 17.1. The proof resembles that of Theorem 2.17. Consider an execution E =(γ0 , γ1 , . . .) of S. If E is finite, its last configuration is terminal and belongs to L by (1).Otherwise, consider the sequence (f (γ0 ), f (γ1 ), . . .); as there are no infinite decreasing sequences in W , there is an i such that f (γi ) > f (γi+1 ) does not hold.

By (2), γi+1 ∈ L.Exercise 17.2. In the initial state F is at most 21 N (N − 1), and every step of process 0increases F by at most N − 1 (if it gives privilege to process 1). So the number of steps byprocesses other than 0 before the (N + 1)th step of process 0 is bounded by 21 N (N − 1) +N (N − 1), which brings the total number of steps to at most 23 N (N − 1) + N .A suitable norm function is defined as follows [DHS+ 94, Sec. 6.2]. Call configuration γsingle-segment if there exists j < N such that for all i ≤ j : σi = σ0 and for all i > j : σi 6= σ0 .Defineif γ is single segment 0the smallest i s.t.σ0 + iA(γ) =does not occur in γotherwiseand W (γ) by W (γ) = N.A(γ) + F (γ). For each step γ → δ, [W (γ) > W (δ) ∨ δ ∈ L] holds.Exercise 17.4.

Modify action (1) so that the idle process p will receive the token only if pand q are oriented differently; if they are oriented the same way, the sending process becomesidle.Action(1a)(1b)qpp→←→I−→←←IS−→SR←IAction (1a) is the same silent step as before, but action (1b) will kill the token where originallyit would be forwarded to a process that already has the same orientation. This ensures thattoken circulation ceases, yet we are still guaranteed to have tokens as long as the ring is notlegitimate (by Proposition 17.9).Exercise 17.6.

Replace the variable pref p by a three-valued variable cpq for each neighborq, with value you if p has selected q, other if p has selected r 6= q, and none if p has not madea selection. These variables satisfy a local consistency:lc(p) ≡(∀q ∈ Neighp : cpq = none)∨ (∃q ∈ Neighp : cpq = you ∧ ∀r 6= q ∈ Neighp : cpr = other ).An additional “clearing” action Cp , executed at most once for every process, establishes localconsistency. Quantifications below run over Neighp .var cpq : (you, other , none);Cp : { ¬lc(p) }forall q do cpq := noneMp : { lc(p) ∧ cpq = none ∧ cqp = you }forall r do cpr := other ; cqp := youSp : { lc(p) ∧ cpq = cqp = none ∧ ∀r 6= q : crp 6= you34forall r do cpr := other ; cqp := youUp : { lc(p) ∧ cpq = you ∧ cqp = other }forall r do cpr := noneEach process is locally consistent after at most one step, and the algorithm then behaves likethe original one.Can you prove a bound on length of an execution? Can you modify the algorithm so asto work for the link-register read-one model?Exercise 17.7.

In each matching step (action Mp ) the value of c+f +w decreases by at least2, and the other steps decrease the value of the second component of F . Hence the functionF = (b(c + f + w)/2c, 2c + f ) is also a norm, and proves stabilization within N 2 + 2 21 N steps.To show the lower bound we inductively construct an execution of 12 k 2 steps on a cliquecontaining k (even) free processes; if k = 2 the two remaining processes are matched in twosteps. If there are k > 2 free processes p1 and p2 , first processes p1 through pk−1 select pk ,then process pk matches pk−1 , and finally processes p1 through pk−2 unchain from pk . Afterthese 2k − 2 steps the network contains k − 2 free processes, so by induction the executioncan be continued for another 12 (k − 2)2 steps.A more precise analysis is found in [Tel94].

A proof of stabilization within O(|E|) stepsis found in [DHS+ 94, Section 7.2].Exercise 17.8. Assume the state read-all model and have a boolean mis p for each p, indicating if p is currently in the set M . There are two actions: (1) if both p and a neighborare in M , mis p := false; (2) if neither p nor any neighbor is in M , mis p := true. Call pblack if (1) applies, gray if (2) applies, and white if neither applies.