Errata for 2nd Edition

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

Last updated: September 19, 2016

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 process 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 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 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 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)
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 thatn ≤ 4f, a contradiction.


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


Page 383, reference 29: (Michael Fu)
Insert
Optimal
before
Clock