Distributed Computing: Fundamentals, Simulations, and Advanced Topics by Attiya and Welch
Last updated: February 4, 2003
This is a list of the known errors, and their corrections, for the first 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@cs.tamu.edu .
Page 12, line -13 through -12: (Krzysztof Parzyszej)
Change
Not every sequence of events is a schedule; for instance, del(1,2,m) is not a schedule since…
to
Not every sequence of events is a schedule for every initial configuration; for instance, del(1,2,m) is not a schedule for an initial configuration with empty outbufs since…
Page 27, Algorithm 2.4, Line 25: (Ajay Kshemkalyani)
Put “leader” in angle brackets.
Page 27, Algorithm 2.4, Line 10: (Antonio Romano)
Add
children := empty
Page 28, line 7: (Marios Mavronicolas)
Change
the message complexity
to
the time complexity.
Page 28, line 8: (Jennifer Walter)
Add
assuming every processor wakes up within constant time.
Page 28, line 16 (hint for Exercise 2.2):
Change
during round t
to
during round t+1.
Page 28, line -6 (Exercise 2.6):
Change
Algorithm 2.1
to
Algorithm 2.2
Page 37, Line 4 of Algorithm 3.1: (Lucia Dale)
Change
(probe,id,1,0)
to
(probe,id,0,1)
Page 37, Line 15 of Algorithm 3.1: (Lucia Dale)
Change
(probe,id,l+1,0)
to
(probe,id,l+1,1)
Page 37, line -1: (Neeraj Koul and Jian Xu)
A 2n term is missing from the sum, due to the last round, during which the leader sends probe messages all around the ring in both directions.
Page 46, Algorithm 3.2: (Jian Chen)
Replace incorrect pseudocode with corrected pseudocode.
Page 58, line -12 (hint for Exercise 3.10): (Ted Herman)
Change
all-zeroes ring
to
all-ones ring
Page 58, line -11 (hint for Exercise 3.10): (Ted Herman)
Change
single 1
to
single 0
Page 66, Figure 4.1: (Ted Herman)
Exchange Entry with Critical
Page 73, Line 4 of Algorithm 4.3: (Lucia Dale)
Change
for j := 1 to n (=/= i) do
to
for j := 0 to n-1 (=/= i) do
Page 83, Figure 4.7: (Jennifer Walter)
Exchange the tau and pi edge labels, in both places.
Page 84, Figure 4.8: (Jennifer Walter)
Change
alpha’
to
pi’
Page 86, Figure 4.10: (Jennifer Walter)
Change
alpha’
to
pi’
Pages 87-88: (Jennifer Walter)
Fast-lock and Slow-lock must be initialized to -1, not 0, since 0 is a processor id. Thus 0 should be replaced with -1 in the following places:
- Algorithm 4.7: Initialization line, Line 3, Line 5, Line 12, Line 14.
- Page 87, line -1 (first occurrence)
- Page 88, line 3
Page 93, line -11:
Change
For crash failures
to
For two-element input sets
Page 103, line 10:
Change
Unlike the crash failures case
to
For input sets whose size is larger than two
Page 123, line 10 (Exercise 5.1):
Change
Show that for crash failures
to
Show that for two-element input sets
Page 124, Algorithm 5.4: (Iyad Kanj)
Change
round k, 1 <= k <= f/k + 1:
to
round r, 1 <= r <= f/k + 1:
Page 124, Algorithm 5.4, Line 4: (Iyad Kanj)
Change
if k = f + 1
to
if r = f/k + 1
Page 124, line -13 (Exercise 5.6):
Change
k-consensus
to
k-set consensus
Page 124, lines 7 ff. (Exercise 5.7):
Change
Show that the validity condition for Byzantine failures, given in Section 5.2.2, is not equivalent to requiring that every nonfaulty decision be the input of some processor.
to
Show that the validity condition given in Section 5.2.2 is not equivalent to requiring that every nonfaulty decision be the input of some processor, if the input set has more than two elements.
Page 125, line 20. (Exercise 5.15): (Jennifer Walter)
Change
asynchronous system subject to a single crash failure.
to
asynchronous system.
Page 126, Exercise 5.18:
Replace with
Consider an asynchronous shared memory system in which there are only test&set registers (as defined in Chapter 4) and two processors. Show that it is possible to solve consensus in this system even if one processor can crash.
Page 126, line 15. (Exercise 5.19):
Change
solved in a system
to
solved in an asynchronous shared memory system
Page 131, line -5: (Erich Mikk)
Change
execution fragment
to
execution segment
Page 137, line -5: (James Aspnes)
Change
ordered lexicographically
to
ordered component-wise
Page 142, lines 1-2: (Maurice Herlihy)
The store array must also record the contents of the messages received in order for replay to be possible.
Page 152, Algorithm 6.2, Line 4: (Marios Mavronicolas)
Change
diff[j]
to
diff[k]
Page 155, Exercise 6.5: (Srikanta T.N)
Change
a maximal consistent cut
to
a unique maximal consistent cute
Page 156, Figure 6.15: (Jian Chen)
Subtract u from each delay.
Page 156, line -14 (Problem 6.11):
Change
Show that the skew of this algorithm is d/2, when d is the upper bound on message delay.
to
Show that the skew of this algorithm is u/2, where u is the uncertainty of the message delay.
Page 174, line 1: (Mark Handy)
Change
– the bc-recv event
to
– every bc-recv event
Page 181, line 2: (Mark Handy)
Change
and v to
to
and v[k] to
Page 181, line 3: (Mark Handy)
Change
Exercise 8.6
to
Exercise 8.7
Page 181, Algorithm 8.2, Line 10: (Mark Handy)
Change the last character on the line from i to j.
Page 182, lines 11-14:
The i and j subscripts were reversed. It should read:
This means that some message m’ sent by pj before m has not been (causally) received by pi, and in the latter case, some message m’ (causally) received at pj before sending 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, Line 17:
Change
satisfy the same
to
satisfy essentially the same
Page 191, Exercise 8.6: (Mark Handy)
Change
Algorithm 8.1
to
the asymmetric algorithm of Section 8.2.3
Page 191, Exercise 8.10: (James Aspnes)
Change
reduction to the consensus problem
to
reduction from the consensus problem
Page 197, Figure 9.2:
The end of p1’s write should precede the beginning of p0’s read.
Page 200, Figure 9.3:
The label on the top dotted line should be pj instead of pi.
Page 202, line 6:
Change
latest to
later
Page 209, Exercise 9.6:
Change
For each e between 0 and d
to
For each e between 0 and u
Page 217, Figure 10.2:
The high-level write of 1 should include a low-level write of 0 to B[3] after the low-level write of 1 to B[1].
Page 227, Algorithm 10.3, Line 2 of read:
Change
max{t[1],…,t[m]}
to
max{t[0],…,t[m-1]}
Page 227, Algorithm 10.3, Line 1 of NewCTS:
Change
for i := 1 to m do
to
for i := 0 to m-1 do
Page 308, line 3:
Change
c . n
to
(1/c) . n
Page 347, Exercise 15.6:
Both occurrences of “consensus algorithm” should read “wait-free consensus algorithm”.
Page 349, line 8:
Change
at a lower level can be used
to
at a lower level cannot be used
Page 374, Algorithm 16.6, Line 2 of read:
Change
vts[1],…,vts[m]
to
vts[0],…,vts[m-1]
Page 389, line -2:
Change
round to executed
to
rounds to execute
Page 393, line -6:
Change
snapshot
to
scan
Page 394, line 2:
Change
during alpha’.
to
once every trying processor has done an update based on a scan that started in alpha’.
Page 402, Exercise 17.19:
This exercise is wrong.
See this note for exponential execution examples.
Page 403, line -15:
Insert reference to
CHAUDHURI, S., More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105, 1 (July 1993), 132–148.
Page 403, line -14:
Change
f <= k
to
f < k
Page 403, line -13:
Change
f > k
to
f >= k