Errata for
Distributed Computing: Fundamentals, Simulations, and Advanced Topics, Second Edition by Attiya and Welch
Last updated: January 19, 2022
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 pj then send < M > to all neighbors except pj else terminate
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 pj-only.
Page 98, Figure 5.3: (Christian Walter, Asad Chaudhry)
In the second extension, αkj, pj fails to send to q1, …, qj (and not q1, …, qi, 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
pj must first (causally) receive all messages (causally) received by pi before sending m
with
pj must first (causally) receive all messages that were (causally) received by pi before pi sent m
Page 176, line −6:
replace
Exercise 8.6
with
Exercise 8.7
Page 177, lines 9−12:
Swap the roles of pi and pj. That is, replace
some message m’ … pending set.
with
some message m’ sent by pj before pj sent m has not been (causally) received by pi, and in the latter case, some message m’ (causally) received at pj before pj sent 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, Exercise 8.1:
Only consider the failure-free case.
Page 202, Figure 9.5: (Antal Buss)
Swap the labels p0 and p2 in parts (a) and (b) of the figure so that p0 is the writer and p2 is one of the readers.
Page 203, Exercise 9.6:
Replace u with d
Page 213, line −6: (Hadi Asghari-Moghaddam, Andre Lami)
Replace v1 with v
Page 214, last line: (Duong Nguyen)
Replace
R cannot read from W’
with
R2 cannot read from W2
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 229, line −2: (Duong Nguyen)
replace
<
with
≤
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 rmax ≥ maxRound
with
until rmax ≥ 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 Rj in lines 5−9 do not need to be five separate reads of Rj: it is sufficient to read Rj once during this for loop and save the value in a local variable. However, the read of Rj in line 12 must be a separate read.
Page 371, line 5 of Algorithm 59:
Change
Rj.phase-tag
to
Rj.phase
Page 373, line −2:
Change
according to Ri.phase
to
according to the local r variable
Page 374, line 7 of Algorithm 60:
Change
Rc.phase ≥ r
to
Rc.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