## Errata for

*Distributed Computing: Fundamentals, Simulations, and Advanced Topics, Second Edition *by Attiya and Welch

## Last updated: June 10, 2019

This is a list of the known errors, and their corrections, for the second 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@cse.tamu.edu .

**Page 18, line 5:** (Panagiota Fatourou)

*Change*

in round *t*

*to*

by time *t*

**Page 22, line 9 of Algorithm 2:** (Panagiota Fatourou, Ruediger Valk)

*replace Line 9 with*

if there are neighbors besides *p _{j}* then send <

*M*> to all neighbors except

*p*else terminate

_{j}**Page 28, Exercise 2.11:** (Panagiota Fatourou, Simran Dokania)

*Change*

Algorithm 3

*to*

Algorithm 4

**Page 37, Algorithm 5, Line 15:** (Panagiota Fatourou)

*Change*

send < probe, *id, k+1,1* >

*to*

send < probe, *id, k+1,1* > to left and right

**Page 41, line −13** (Bashar)

*“because” is misspelled.*

**Page 42, line 1**

*Change alpha to sigma, i.e.,*

α’_{4}

*to*

σ’_{4}

**Page 45, Algorithm 6** (Bashar)

*Line numbering is incorrect (line numbers 9 and 10 are repeated).*

**Page 45, Algorithm 6, Line 20** (Bashar)

*Change*

remove < *m* >

*to*

remove < *m*,2 >

**Page 49, line 16** (Bashar)

*Change*

that that

*to*

that

**Pages 68−69, Lemma 4.3**

*The invariants given are not sufficient/correct to prove the correctness of the algorithm. Finding the correct invariants is left as an exercise.*

**Page 74, line −9:** (Panagiota Fatourou)

*Change*

As proved Theorem

*to*

As proved in Theorem

**Page 79, line 9:**

*Change*

the same is true of α_{v}

*to*

no processor stays in the critical section forever in α_{v}

**Page 81, Figure 4.8:**

*Both occurrences of τ should be labeled as P-only, while both occurrences of π should be labeled as p _{j}-only.*

**Page 98, Figure 5.3:** (Christian Walter, Asad Chaudhry)

*In the second extension, α _{k}^{j}, p_{j} fails to send to q_{1}, …, q_{j} (and not q_{1}, …, q_{i}, as shown).*

**Page 116, beginning of third paragraph:** (Hirokazu Honda)

*replace*

*k ≤ 1*

*with*

*k ≥ 1*

**Page 121, Exercise 5.9:**:

*Construct the execution for n = 8 and f = 2.*

**Page 134, definition of cut:**:

*replace*

positive integers

*with*

nonnegative integers (0 means initial state)

**Page 150, line 20:**:

*replace*

error is at most half of *d’ − (d − u)*, or *u/2 − (d − d’)/2*, which is less than *d’/2*

*with*

error is at most *d’ − (d − u)*, which is less than *d’*

**Page 150, line −5:**:

*replace*

*u/2 − (d − d’)/2* *with*

*d’ − (d − u)*

**Page 151, Exercise 6.5:**:

*replace*

preceding

*with*

equal to or preceding

**Page 176, Algorithm 22 line 10:** (David Van Cleve)

*replace*

*k ≠ i*

*with*

*k ≠ j*

**Page 176, lines 6−7:**

*replace*

*p _{j}* must first (causally) receive all messages (causally) received by

*p*before sending

_{i}*m*

*with*

*p*must first (causally) receive all messages that were (causally) received by

_{j}*p*before

_{i}*p*sent

_{i}*m*

**Page 176, line −6:**

*replace*

Exercise 8.6

*with*

Exercise 8.7

**Page 177, lines 9−12:**

*Swap the roles of p _{i} and p_{j}. That is, replace*

some message

*m’*…

*pending*set.

*with*

some message

*m’*sent by

*p*before

_{j}*p*sent

_{j}*m*has not been (causally) received by

*p*, and in the latter case, some message

_{i}*m’*(causally) received at

*p*before

_{j}*p*sent

_{j}*m*has not been (causally) received by

*p*. in both cases, by the Liveness properties of the underlying broadcast service,

_{i}*m’*must be stuck in

*p*‘s

_{i}*pending*set.

**Page 185, Exercise 8.1:**

*Only consider the failure-free case.*

**Page 202, Figure 9.5:** (Antal Buss)

*Swap the labels p _{0} and p_{2} in parts (a) and (b) of the figure so that p_{0} is the writer and p_{2} is one of the readers.*

**Page 203, Exercise 9.6:**

*Replace u with d*

**Page 213, line −6:** (Hadi Asghari-Moghaddam, Andre Lami)

*Replace v _{1} with v*

**Page 219, last paragraph of proof of Lemma 10.4:**

*Change both occurrences of Report[i] to Report[j].*

**Page 222, line 5:** (Christian Cachin)

*replace*

*w’* occurs in α after *r*

*with*

*w’* occurs in α before *r*

**Page 235, Exercise 10.12:**

*replace
f < 2n
with
f < n/2*

**Page 240, line 2:** (Michael Fu)

*Change*

from the synchronous system to the asynchronous system

*to*

from the asynchronous system to the synchronous system

**Page 258, end of proof of Theorem 12.1:** (Michael Fu, Honda)

*Replace the last two sentences with*

Thus the total number of processors, *n*, is at least the total number of nonfaulty processors, which is at least *2(n−2f)*; that is, *n ≥ 2(n−2f)*. This implies that *n ≤ 4f*, a contradiction.

**Page 351, line −3:**

*Replace*

as long as *f > n/2*. If *f ≤ n/2*

*with *

as long as *f < n/2*. If *f ≥ n/2*

**Page 355, Algorithm 54, line 8:** (Jim Aspnes)

*Replace*

until *r _{max} ≥ maxRound*

*with*

until

*r*max

_{max}≥*(2,maxRound)*

**Page 363, Algorithm 58:** (Danny Hendler)

*Similarly to the bakery mutual exclusion algorithm, Lines 1−2 (in which a process reads the other numbers and writes its own) should be wrapped with *

waiting[*i*] := true,

*and*

waiting[*i*] := false

*Comparing the number with j should wait until waiting[j] is false.*

**Page 371, line 2 (signature of procedure safe-phase):** (Michel Raynal)

*Reverse the order of the parameters to procedure safe-phase. I.e., change*

value *x*, integer *r*

*to*

integer *r*, value *x*

**Page 371, Algorithm 59:**

*The five references to R _{j} in lines 5−9 do not need to be five separate reads of R_{j}: it is sufficient to read R_{j} once during this for loop and save the value in a local variable. However, the read of R_{j}in line 12 must be a separate read.*

**Page 371, line 5 of Algorithm 59:**

*Change*

*R _{j}.phase-tag*

*to*

*R*

_{j}.phase**Page 373, line −2:**

*Change*

according to *R _{i}.phase*

*to*

according to the local

*r*variable

**Page 374, line 7 of Algorithm 60:**

*Change*

*R _{c}.phase ≥ r*

*to*

*R*

_{c}.phase > r**Page 374, line −7:**

*Change*

asynchronous system

*to*

asynchronous message-passing system

**Page 374, line −7:** (Michel Raynal)

*Change*

*n ≤ n/2*

*to*

*n ≤ 2f*

**Page 375, statement of Theorem 17.3:**

*Change*

message-passing systems

*to*

asynchronous message-passing systems

**Page 378, Exercise 17.5:**

*Change*

asynchronous system

*to*

asynchronous message-passing system

**Page 383, reference 29:** (Michael Fu)

*Insert*

Optimal

*before *

Clock