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

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.

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.
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

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
"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

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$.