List of corrections for
Introduction to Distributed Algorithms (2nd Ed, 2000)
by Gerard Tel.
P62 L18: omit ) after 3.2.
P120 L-9: at most N-1 rounds
P122 L-6: aN unfavorable way
P125 L8: Following this line, add the comment
(* It suffices actually to do this for v s.t. Nb_u[v] = w *)
Sec 5.3.1: As the value of s_p (or t_p) depends not only on
the packet p, but also on the location, the exposition
will be clearer if the notation s_p[u] is used.
P170 L-1,-2: then should be than, three times!
P253, Alg 7.10: in (2), add after "else if stach_p[q] = basic"
this: "or L > level_p".
P266 Exer 7.2: Show that, for D > 1, ...
P269 L-15: Add "A full characterisation of solvable cases
was given by Chalopin \etal\ \cite[ChGoMeTe07]."
(And in line -5 omit "all".)
P289, L19,20: remove superfluous r and r-
P317, add to statement of Thm 9.5:
"This holds even if executions are fair."
In the proof, L-5/-4, replace ", say event e_i
in p_i" by "; let event $e_i$ in $p_i$ be the
event that has been applicable the longest"
P318, L5: Before "In", add "In the infinite executions,
no event remains unapplied (by the choice of $e_i$),
so these are fair."
P324 L21: add condition " or state_p = lost"
P326 L15: bounded by e.N/(N-1)
P326 L18: Add "Fokkink and Pang \cite{FoPa04} have
shown that if channels are FIFO, level numbers
can be omitted from the messages."
P326, bottom: add "The IEEE 1394 standard
(for the Firewire\index{Firewire} bus) is designed
for networks with identities, but sending them over
the network is considered expensive.
So, the election algorithm in this standard is a
Las Vegas algorithm (on trees)."
P327 L12: space in be the
P328 L2: Add "Because of process termination, this
cannot be corrected later."
P341, above section: remove double period
P351 L-6: The variable
P353 L-9 Replace "the most" by "a very"
P353 L-6: reference is [BHRS95]
p355 L-11: Name of professor is Prlwytzkofsky
P404 L-13 sloution should be solution
P431 L20: ia should be a
P439 L14: exists
P459: In the algorithm, the letter t is used with 2 meanings.
Denote the type of a message by "type".
The same goes for Alg 14.6 on page 464
P460 L-7: replace at least by more than
P464 Exercise 14.11: more than
P473 L-11 algoritm is from Lamport etal [LSP82].
P508 L12: detector
P509 L-1: success
P514 L18: replace "y_i = @" by "no decision was taken"
P514 L-8: write N-2t > (N-t)/2
P520 L-4: Remove "; hence
the subject can be considered relatively new"
P522 L-15: simpler than
P547 L-4 Hoe99 becomes FHP05
P547 L-6: Replace "step of the algorithm" by
"transition from a non-legitimate configuration"
P548 L7 remove ).
P572 L14: Foundations of Computer Science
P574 Ref BHR92: replace by BHRS95:
Brzezinski, J., Helary, J., Raynal, M., and Singhal, M.
Deadlock models and a general algorithm for
distributed deadlock detection.
J. Parallel Distrib. Comput. 31, 2 (Dec. 1995), 112-125.
P579 L-5 Foundations of Computer Science
P579 Replace reference Hoe99 by
W.J. Fokkink, J.-H. Hoepman and J. Pang,
A note on K-state self-stabilization in a ring with K=N,
Nordic Journal of Computing 12(1):18-26 (Spring 2005).
P582 L3: update reference:
Daniel A. Menascé, Richard R. Muntz:
Locking and Deadlock Detection in Distributed Data Bases.
IEEE Trans. Software Eng. 5(3): 195-202 (1979)
P584 Ref Ste99, pages 221 to 225.
References: added for CGMT07, FP04