Remarks by Prof. Yoram Moses

May 2000

Just wanted to say that I'm enjoying your book. 
I'm compiling a list of typos and minor comments. 
One omission that may be worth mentioning is on page 33, 
the proof of the maximal matching algorithm. 
A crucial step is missing from this proof: 
Showing that if a maximal matching has not been 
constructed yet, then progress will be made. 
Thus, for example, in the round following a 
non-maximal configuration, at least one process 
will change the state. 

May 2000 I just finished the first class. A typo and a question: Proof of Lemma 2.1: Why state the claim for k \ge 1, and have the base case k=1? It appears the claim is correct for k=0, and its proof is very simple (because you count Delta + 4kDelta, so even k=0 gives the root Delta write operations to perform). The inductive case is written with " k\ge 0 " whereas you are talking about k \ k\ge 1 here.
June 2000 Thanks very much for the book and your advice. I found the book very well written and both instructive and informative. Here is a short list of typos that I compiled while reading the first two chapters. The will hopefully help for a second printing/edition. Let me know if you have any questions about these comments. Page 15 Proof of Lemma 2.1: I have already given you comments on this. Page 17 Line -14 "reminder" sb "remainder" Page 18, Lemma 2.3: Why make this obvious fact a lemma? It's used only once, and can be stated and argued there. Page 19 Line -13 add commas around "2\le i \le n" Page 19, proof of lemma 2.4: The way I presented it was: Assume exists c and a fair ex'n in which P_1 doesn't change x_1 during the first n-1 rounds. (==You had n rounds==) Claim: at the end of k rounds, 0\le k\le n-1 we have x1=...=x_{k+1}. Then when P_1 is activated in round n it changes the value of x_1. (==this is the same proof you have, but not stated in terms of a pf by contradiction. Just a suggestion.==) Page 25 Line 4 "a Euler" sb "aN Euler" Page 32 First paragraph, the wording is a bit awkward. Why do you say "assume that in c_l there are no two..."? This assumption is not Explicitly used. Page 32, Figure 2.8, Lines 3 and 6: In both cases you set a variable to j, when j is not uniquely determined. It seems that you mean this step to involve nondeterministically choosing one of the j's, but this is not made explicit. Page 33 Line 10,12: in both cases you talk about c_l .s.t. VF(c)=... you probably meant to use the same notation (c or c_l) in a consistent manner. Page 33 As mentioned in a previous msg, the argument that as long as the goal has not been reached one of the steps is applicable is an important part of the proof that is essentially left out. Page 34 Lines 16-17: Instead of "using a centralized computation by that leader" I would prefer to talk about "using this leader as the (centralized) coordinator of a computation solving this task" or something like this. Anyway, the current reading was a bit funny. Page 35, caption for Figure 2.9 missing "a" before "general graph" Page 35 Line -6: You use "l_i[j]" and "d_i[j]" while this notation does not appear in figure 2.9 (probably left over from an earlier version) Page 45 Line 16 "to execution," sb "to AN execution" Page 52 Line -7 "increment" sb "increase". Page 53 Line -5 "ing execution" sb "ing AN execution" Page 53-4 Ex 2.1: I gave this one out to the students. Mistake. The proposal made in the exercise is ILL-defined. You need to say explicitly what the new algorithm is. Is the model changed at all? The state space? This needs to be rewritten from scratch.

Remarks by Prof. Lisa Higham

September 2000

Notes and comments on Self-Stabilization.

Dijkstra's self-stabilizing mutual exclusion algorithm, ME, 
is presented in Chapter 2 section 6. 
These comments and questions apply to it.

1.  On page 20 there is a ring construction and scheduling 
that demonstrates that 3 values (or process states) are 
insufficient for ME to stabilize to a safe configuration 
on a ring of size 5.  
1a.  Describe the more general construction and scheduler 
that demonstrates that $n-2$ values are insufficient for
a ring of size $n$.
1b.  To conclude that ME requires $n-1$ values for a ring
of size $n$, we need to establish that $n-k$ values are
insufficient for \emph{any} $k \geq 2$.  
Describe precisely a ring construction and scheduler that
gives this counterexample.

2. Pages 21-22 describe a simulation of any execution of ME under 
atomic read/write atomicity on a ring of size $n$, by an execution 
of ME under composite atomicity on a ring of size $2n$. 
Use the simulation to give a complete proof that $2n-1$ values 
are necessary and sufficient for ME to stabilize under read/write 
atomicity on a ring of size $n$.