Introduction to Distributed Algorithms - Solutions and Suggestions. Gerald Tel (Introduction to Distributed Algorithms - Solutions and Suggestions. Gerald Tel.pdf)

Introduction to Distributed Algorithms:Solutions and SuggestionsGerard TelDepartment of Computer Science, Utrecht UniversityP.O. Box 80.089, 3508 TB Utrecht, The Netherlandsemail: g.tel@.uu.nlMay 2002/January 2015This booklet contains (partial) solutions to most of the exercises in the book Introductionto Distributed Algorithms [Tel00]. Needless to say, the book as well as this document containnumerous errors; please find them and mail them to me! I have not included answers or hintsfor the following exercises and projects: 2.3, 2.9, 2.10, 3.2, 3.7, 6.16, 10.2, 12.8, 12.10, 12.11,14.6, 17.5, 17.9, 17.11, B.5.Gerard Tel.ContentsChapter 2: The Model .

. . . . . . . . . . . . . . . . .Chapter 3: Communication Protocols . . . . . . . . .Chapter 4: Routing Algorithms . . . . . . . . . . . . .Chapter 5: Deadlock–free Packet Switching . . . . . .Chapter 6: Wave and Traversal Algorithms . .

. . . .Chapter 7: Election Algorithms . . . . . . . . . . . . .Chapter 8: Termination Detection . . . . . . . . . . .Chapter 9: Anonymous Networks . . . . . . . . . . . .Chapter 10: Snapshots . . . . . . . . . . . . . . . . . .Chapter 12: Synchrony in Networks . . . . . . .

. . .Chapter 14: Fault Tolerance in Asynchronous SystemsChapter 15: Fault Tolerance in Synchronous Systems .Chapter 17: Stabilization . . . . . . . . . . . . . . . .Appendix B: Graphs and Networks . . . . . . . . . . .Bibliography . . . . . .

. . . . . . . . . . . . . . . . .1..............................................................................................................................................................................................................................................................................24691217202125262831343638Chapter 2: The ModelExercise 2.1.

Let M1 be the set of messages that can be passed asynchronously, M2the set of messages that can be passed synchronously, and M = M1 ∪ M2 . A process isdefined as in Definition 2.4. A distributed system with hybrid message passing has four typesof transitions: internal, send and receive of asynchronous messages, and communication ofsynchronous messages. Such a system is a transition system S = (C, →, I) where C and Iare as in Definition 2.6 and →= (∪p∈P →p ) ∪ (∪p,q∈P →pq ), where →p are the transitionscorresponding to the state changes of process p and →pq are the transitions correspondingwith a communication from p to q. So, →pi is the set of pairs(cp1 , .

. . , cpi , . . . , cpN , M1 ), (cp1 , . . . , c0pi , . . . , cpN , M2 )for which one of the following three conditions holds.• (cpi , c0pi ) ∈ `ipi and M1 = M2 ;• for some m ∈ M1 , (cpi , m, c0pi ) ∈ `spi and M2 = M1 ∪ {m};• for some m ∈ M1 , (cpi , m, c0pi ) ∈ `rpi and M1 = M2 ∪ {m}.Similarly, →pi pj is the set of pairs(. . . , cpi , .

. . , cpj , . . .), (. . . , c0pi , . . . , c0pj , . . .)for which there is a message m ∈ M2 such that(cpi , m, c0pi ) ∈ `spiand (cpj , m, c0pj ) ∈ `rpj .Exercise 2.2. Consider the system S = ({γ, δ}, {(γ → δ)}, ∅), and define P to be true in γbut false in δ. As there are no initial configurations, this system has no computations, hencetrivially P is always true in S.

On the other hand, P is falsified in the only transition of thesystem, so P is not invariant.If an empty set of initial configurations is not allowed, the three state system S 0 =({β, γ, δ}, {(γ → δ)}, {β} is the minimal solution.The difference between invariant and always true is caused by the existence of transitionsthat falsify a predicate, but are applicable in an unreachable configuration, so that they donot “harm” any computation of the system.Exercise 2.4. (1) If each pair (γ, δ) in →1 satisfies P (γ) ⇒ P (δ) and each such pair in →2does so, then each pair in the union satisfies this relation.(2) Similarly, if (Q(γ) ∧ P (γ)) ⇒ (Q(δ) ⇒ P (δ)) holds for each pair (γ, δ) in →1 and in →2 ,then it holds for each pair in the union.(3) In the example, P is an invariant of S1 , and always true in S2 , but is falsified by atransition of S2 which is unreachable in S2 but reachable in S1 .

This occurs when S1 =({γ, δ, }, {(γ → δ)}, {γ}) and S2 = ({γ, δ, }, {(δ → )}, {γ}) with the assertion P , whichis false in .Exercise 2.5. In (N2 , ≤l ), (1, k) <l (2, 0) for each k; hence there are infinitely many elementssmaller than (2, 0).It is shown by induction on n that (Nn , ≤l ) is well-founded.2n = 1: N1 is identical to N, which is well-founded.n + 1: Assume (Nn , ≤l ) is well-founded and w is an ascending sequence in the partial order(N(n+1) , ≤l ). Partition the sequence in subsequences, i.e., write w = w1 .w2 .

. . ., whereeach wi is a maximal subsequence of elements of w that have the same first component.The number of these subsequences is finite; because w is ascending, the first componentof elements in wi+1 is smaller than the first component of elements in wi . Each wi isof finite length; because w is ascending and consecutive elements of wi have the samefirst component, the tail of each element (which is in Nn ) is smaller than the tail of itspredecessor in wi . The well–foundedness of Nn implies that wi is finite.

As w is theconcatenation of a finite number of finite sequences, w is finite.Exercise 2.6. The event labels:a1ΘLΘv1000b22000c53200d32100e42200f21010g31020h41030i81043j51031k61032l71033Events d andg areconcurrent;while ΘL (d) = ΘL (g) = 3, the vector time stamps Θv (d) andΘv (g),2100and1020,are incomparable.Exercise 2.7. The algorithm (see also [Mat89]) resembles Algorithm 2.3, but maintains avector θp [1..N ].

An internal event in p increments p’s own component of the vector, i.e.,preceding an internal event, p executesθp [p] := θp [p] + 1.The same assignment precedes a send event, and as in Algorithm 2.3 the time stamp isincluded in the message.Finally consider a receive event r following an event e in the same process, and withcorresponding send event s. The history of r consists of the combined histories of e and s,and the event r itself; hence the clock is updated byforall q do θp [q] := max(θp [q], θ[q]) ;θp [p] := θp [p] + 1Exercise 2.8. For finite executions E and F this is possible, but for infinite executions thereis the problem that no finite number of applications of Theorem 2.19 suffices. We can thenobtain each finite prefix of F by applying 2.19, but as we don’t have “convergence results”,this would not prove Theorem 2.21.3Chapter 3: Communication ProtocolsExercise 3.1.

Assume a configuration where packets sp and sp + 1 are sendable by q, but qstarts to send packet sp + 1 infinitely often (and the packet is received infinitely often). Thisviolates F1 because packet sp remains sendable forever, but F2 is satisfied, and no progressis made.Exercise 3.3. (1) The steps in the execution are as follows:1.2.3.4.5.6.The sender opens and sends h data, true, 0, x i.The receiver receives the packet, opens, and delivers.The receiver sends h ack, 1 i, but this message is lost.Sender and receiver repeat their transmissions, but all messages are lost.The receiver times out and closes.The sender times out and reports data item 0 as lost.(2) No, this is not possible! Assume a protocol in which response is guaranteed withing ρtime, and assume q will deliver the data upon receipt of a message M from p.

Consider twoexecutions: E1 in which M is lost and no messages are received by p for the next ρ time units;E2 in which q receives M and no messages are received by p for the next ρ time units. Processq delivers m in E2 but not in E1 . To p, E1 and E2 are identical, so p undertakes the sameaction in the two executions. Reporting is inappropriate in E2 , not doing so is inappropriatein E1 ; consequently, no protocol reports if and only if the message is lost.Exercise 3.4. In the example, the sender reuses a sequence number (0) in a new connection,while the receiver regards it as a duplicate and does not deliver, but sends an ack.1.2.3.4.5.6.7.8.9.10.11.The sender opens and sends h data, true, 0, x i.The receiver receives the packet, opens, and delivers.The receiver sends h ack, 1 i.The sender receives the acknowledgement.The sender times out and closes.The sender opens and sends h data, true, 0, y i.The receiver (still open!) receives the packet, observes i = Exp − 1and does nothing.The receiver sends h ack, 1 i.The sender receives the acknowledgement.The sender times out and closes.The receiver finally times out and closes.Observe that, with correct timers, this scenario does not take place because the receiveralways times out before the sender does so.Exercise 3.5.

Let the receiver time out and the sender send a packet with the start-ofsequence bit true:41.2.3.4.5.6.7.8.9.10.11.TheTheTheTheTheTheTheTheTheTheThesender opens and sends h data, true, 0, x i.receiver receives the packet, opens, and delivers.receiver sends h ack, 1 i.sender receives the acknowledgement (now Low = 1).receiver times out and closes.sender accepts new data and sends h data, true, 1, y i.receiver receives the packet, opens, and delivers.receiver sends h ack, 2 i.sender receives the acknowledgement (now Low = 2).receiver times out and closes.sender times out and closes.Exercise 3.6.