Remarks on Self-Stabilization by Prof. Shlomi Dolev

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. 

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