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.
Page 18, line 5: (Panagiota Fatourou)
in round t
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)
Page 37, Algorithm 5, Line 15: (Panagiota Fatourou)
send < probe, id, k+1,1 >
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.,
Page 45, Algorithm 6 (Bashar)
Line numbering is incorrect (line numbers 9 and 10 are repeated).
Page 45, Algorithm 6, Line 20 (Bashar)
remove < m >
remove < m,2 >
Page 49, line 16 (Bashar)
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)
As proved Theorem
As proved in Theorem
Page 79, line 9:
the same is true of αv
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)
k ≤ 1
k ≥ 1
Page 121, Exercise 5.9::
Construct the execution for n = 8 and f = 2.
Page 134, definition of cut::
nonnegative integers (0 means initial state)
Page 150, line 20::
error is at most half of d’ − (d − u), or u/2 − (d − d’)/2, which is less than d’/2
error is at most d’ − (d − u), which is less than d’
Page 150, line −5::
u/2 − (d − d’)/2 with
d’ − (d − u)
Page 151, Exercise 6.5::
equal to or preceding
Page 176, Algorithm 22 line 10: (David Van Cleve)
k ≠ i
k ≠ j
Page 176, lines 6−7:
pj must first (causally) receive all messages (causally) received by pi before sending m
pj must first (causally) receive all messages that were (causally) received by pi before pi sent m
Page 176, line −6:
Page 177, lines 9−12:
Swap the roles of pi and pj. That is, replace
some message m’ … pending set.
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)
R cannot read from W’
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)
w’ occurs in α after r
w’ occurs in α before r
Page 229, line −2: (Duong Nguyen)
Page 235, Exercise 10.12:
f < 2n
f < n/2
Page 240, line 2: (Michael Fu)
from the synchronous system to the asynchronous system
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:
as long as f > n/2. If f ≤ n/2
as long as f < n/2. If f ≥ n/2
Page 355, Algorithm 54, line 8: (Jim Aspnes)
until rmax ≥ maxRound
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,
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
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:
Page 373, line −2:
according to Ri.phase
according to the local r variable
Page 374, line 7 of Algorithm 60:
Rc.phase ≥ r
Rc.phase > r
Page 374, line −7:
asynchronous message-passing system
Page 374, line −7: (Michel Raynal)
n ≤ n/2
n ≤ 2f
Page 375, statement of Theorem 17.3:
asynchronous message-passing systems
Page 378, Exercise 17.5:
asynchronous message-passing system
Page 383, reference 29: (Michael Fu)