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

Last updated: Jan 13, 2014

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_j else terminate
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'_4
to
sigma'_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
Page 69, invariant 3 (Keren Censor)
Change
(k - Last - 1) mod n
to
(Last - k) mod n
and add to the end
spinning on Flags[k], Flags[k+1 mod n], ..., Flags[Last-1 mod n]
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 alpha_v
to
no process stays in the critical section forever in alpha_v

Page 81, Figure 4.8:
Both occurrences of tau should be labeled as P-only, while both occurrences of pi should be labeled as p_j-only.


Page 98, Figure 5.3: (Christian Walter, Asad Chaudhry)
In the second extension, alpha_k^j, p_j fails to send to q_1, ..., q_j (and not q_1, ..., q_i, as shown).


Page 121, Exercise 5.9::
Construct the execution for n = 8 and f = 2.


Page 176, lines 6-7:
replace
p_j must first (causally) receive all messages (causally) received by p_i before sending m
with
p_j must first (causally) receive all messages that were (causally) received by p_i before p_i sent m


Page 176, line -6:
replace
Exercise 8.6
with
Exercise 8.7


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 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 alpha after r
with
w' occurs in alpha before r


Page 235, Exercise 10.12:
replace
f < 2n
with
f < n/2


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: (Michel Raynal)
Change
n <= n/2
to
n <= 2f