# Distributed Computing: Fundamentals, Simulations, and Advanced Topics by Attiya and Welch

**Last updated: February 4, 2003**

This is a list of the known errors, and their corrections, for the first edition of *Distributed Computing: Fundamentals, Simulations and Advanced Topics*.

Page and line numbers are used to identify the location of the error; a negative line number means counting from the bottom up. The first person to report the error is credited.

Send corrections to hagit@cs.technion.ac.il or welch@cs.tamu.edu .

**Page 12, line -13 through -12:**(Krzysztof Parzyszej)

*Change*

Not every sequence of events is a schedule; for instance,

*del(1,2,m)*is not a schedule since…

*to*

Not every sequence of events is a schedule for every initial configuration; for instance,

*del(1,2,m)*is not a schedule for an initial configuration with empty

*outbuf*s since…

**Page 27, Algorithm 2.4, Line 25:** (Ajay Kshemkalyani)

*Put “leader” in angle brackets.*

**Page 27, Algorithm 2.4, Line 10:** (Antonio Romano)

*Add*

children := empty

**Page 28, line 7:** (Marios Mavronicolas)

*Change*

the message complexity

*to*

the time complexity.

**Page 28, line 8:** (Jennifer Walter)

*Add*

assuming every processor wakes up within constant time.

**Page 28, line 16 (hint for Exercise 2.2):**

*Change*

during round t

*to*

during round t+1.

**Page 28, line -6 (Exercise 2.6):**

*Change*

Algorithm 2.1

*to*

Algorithm 2.2

**Page 37, Line 4 of Algorithm 3.1:** (Lucia Dale)

*Change*

(probe,id,1,0)

*to*

(probe,id,0,1)

**Page 37, Line 15 of Algorithm 3.1:** (Lucia Dale)

*Change*

(probe,id,l+1,0)

*to*

(probe,id,l+1,1)

**Page 37, line -1:** (Neeraj Koul and Jian Xu)

*A 2n term is missing from the sum, due to the last round, during which the leader sends probe messages all around the ring in both directions.*

**Page 46, Algorithm 3.2:** (Jian Chen)

*Replace incorrect pseudocode with corrected pseudocode.*

**Page 58, line -12 (hint for Exercise 3.10):** (Ted Herman)

*Change*

all-zeroes ring

*to*

all-ones ring

**Page 58, line -11 (hint for Exercise 3.10):** (Ted Herman)

*Change*

single 1

*to*

single 0

**Page 66, Figure 4.1:** (Ted Herman)

*Exchange* Entry *with* Critical

**Page 73, Line 4 of Algorithm 4.3:** (Lucia Dale)

*Change*

for j := 1 to n (=/= i) do

*to*

for j := 0 to n-1 (=/= i) do

**Page 83, Figure 4.7:** (Jennifer Walter)

*Exchange the tau and pi edge labels, in both places.*

**Page 84, Figure 4.8:** (Jennifer Walter)

*Change*

alpha’

*to*

pi’

**Page 86, Figure 4.10:** (Jennifer Walter)

*Change*

alpha’

*to*

pi’

**Pages 87-88:** (Jennifer Walter)

*Fast-lock and Slow-lock must be initialized to -1, not 0, since 0 is a processor id. Thus 0 should be replaced with -1 in the following places:*

*Algorithm 4.7: Initialization line, Line 3, Line 5, Line 12, Line 14.**Page 87, line -1 (first occurrence)**Page 88, line 3*

**Page 93, line -11:**

*Change*

For crash failures

*to*

For two-element input sets

**Page 103, line 10:**

*Change*

Unlike the crash failures case

*to*

For input sets whose size is larger than two

**Page 123, line 10 (Exercise 5.1):**

*Change*

Show that for crash failures

*to*

Show that for two-element input sets

**Page 124, Algorithm 5.4:** (Iyad Kanj)

*Change*

round k, 1 <= k <= f/k + 1:

*to*

round r, 1 <= r <= f/k + 1:

**Page 124, Algorithm 5.4, Line 4:** (Iyad Kanj)

*Change*

if k = f + 1

*to*

if r = f/k + 1

**Page 124, line -13 (Exercise 5.6):**

*Change*

k-consensus

*to*

k-set consensus

**Page 124, lines 7 ff. (Exercise 5.7):**

*Change*

Show that the validity condition for Byzantine failures, given in Section 5.2.2, is not equivalent to requiring that every nonfaulty decision be the input of some processor.

*to*

Show that the validity condition given in Section 5.2.2 is not equivalent to requiring that every nonfaulty decision be the input of some processor, if the input set has more than two elements.

**Page 125, line 20. (Exercise 5.15):** (Jennifer Walter)

*Change*

asynchronous system subject to a single crash failure.

*to*

asynchronous system.

**Page 126, Exercise 5.18:**

*Replace with*

Consider an asynchronous shared memory system in which there are only test&set registers (as defined in Chapter 4) and two processors. Show that it is possible to solve consensus in this system even if one processor can crash.

**Page 126, line 15. (Exercise 5.19):**

*Change*

solved in a system

*to*

solved in an asynchronous shared memory system

**Page 131, line -5:** (Erich Mikk)

*Change*

execution fragment

*to*

execution segment

**Page 137, line -5:** (James Aspnes)

*Change*

*ordered lexicographically*

*to*

*ordered component-wise*

**Page 142, lines 1-2:** (Maurice Herlihy)

*The store array must also record the contents of the messages received in order for replay to be possible.*

**Page 152, Algorithm 6.2, Line 4:** (Marios Mavronicolas)

*Change*

*diff[j]*

*to*

*diff[k]*

**Page 155, Exercise 6.5:** (Srikanta T.N)

*Change*

a maximal consistent cut

*to*

a unique maximal consistent cute

**Page 156, Figure 6.15:** (Jian Chen)

*Subtract u from each delay.*

**Page 156, line -14 (Problem 6.11):**

*Change*

Show that the skew of this algorithm is *d/2*, when *d* is the upper bound on message delay.

*to*

Show that the skew of this algorithm is *u/2*, where *u* is the uncertainty of the message delay.

**Page 174, line 1:** (Mark Handy)

*Change*

– the bc-recv event

*to*

– __every__ bc-recv event

**Page 181, line 2:** (Mark Handy)

*Change*

and *v* to

*to*

and *v[k]* to

**Page 181, line 3:** (Mark Handy)

*Change*

Exercise 8.6

*to*

Exercise 8.7

**Page 181, Algorithm 8.2, Line 10:** (Mark Handy)

*Change the last character on the line from i to j.*

**Page 182, lines 11-14:**

*The i and j subscripts were reversed. It should read:*

This means that some message *m’* sent by *pj* before *m* has not been (causally) received by *pi*, and in the latter case, some message *m’* (causally) received at *pj* before sending *m*, has not been (causally) received by *pi*. In both cases, by the Liveness properties of the underlying broadcast service, *m’* must be stuck in *pi*‘s *pending* set.

**Page 185, Line 17:**

*Change*

satisfy the same

*to*

satisfy essentially the same

**Page 191, Exercise 8.6:** (Mark Handy)

*Change*

Algorithm 8.1

*to*

the asymmetric algorithm of Section 8.2.3

**Page 191, Exercise 8.10:** (James Aspnes)

*Change*

reduction to the consensus problem

*to*

reduction __from__ the consensus problem

**Page 197, Figure 9.2:**

*The end of p1’s write should precede the beginning of p0’s read.*

**Page 200, Figure 9.3:**

*The label on the top dotted line should be pj instead of pi.*

**Page 202, line 6:**

*Change*

latest *to*

later

**Page 209, Exercise 9.6:**

*Change*

For each *e* between 0 and *d*

*to*

For each *e* between 0 and *u*

**Page 217, Figure 10.2:**

*The high-level write of 1 should include a low-level write of 0 to B[3] after the low-level write of 1 to B[1].*

**Page 227, Algorithm 10.3, Line 2 of read:**

*Change*

max{*t*[1],…,*t*[*m*]}

*to*

max{*t*[0],…,*t*[*m*-1]}

**Page 227, Algorithm 10.3, Line 1 of NewCTS:**

*Change*

for *i* := 1 to *m* do

*to*

for *i* := 0 to *m*-1 do

**Page 308, line 3:**

*Change*

*c . n*

*to*

*(1/c) . n*

**Page 347, Exercise 15.6:**

*Both occurrences of “consensus algorithm” should read “wait-free consensus algorithm”.*

**Page 349, line 8:**

*Change*

at a lower level can be used

*to*

at a lower level cannot be used

**Page 374, Algorithm 16.6, Line 2 of read:**

*Change*

*vts*[1],…,*vts*[*m*]
*to*

*vts*[0],…,*vts*[*m-1*]

**Page 389, line -2:**

*Change*

round to executed

*to*

rounds to execute

**Page 393, line -6:**

*Change*

snapshot

*to*

scan

**Page 394, line 2:**

*Change*

during alpha’.

*to*

once every trying processor has done an update based on a scan that started in alpha’.

**Page 402, Exercise 17.19:**

This exercise is wrong.

See this note for exponential execution examples.

**Page 403, line -15:**

*Insert reference to*

CHAUDHURI, S., More *choices* allow more *faults*: Set consensus problems in totally asynchronous systems. *Information and Computation, 105*, 1 (July 1993), 132–148.

**Page 403, line -14:**

*Change*

*f* <= *k*

*to*

*f* < *k*

**Page 403, line -13:**

*Change*

*f* > *k*

*to*

*f* >= *k*