Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456

Address: [go: Go Back, main page]
Remove Scripts Accept Cookies Show Images Show Referer Rotate13 Base64 Strip Meta Strip Title Session Cookies

A Feynmann Quotation and a Short Paper by Fokkink, Hoepman and Pang

27 August 2004

I like quotations --- in fact, probably overly so, as I have been told that I have a tendency to use them too often in my talks. One that I use on the recent publications page for Anna Ingólfsdóttir and me is the following:

If you keep proving stuff that others have done, getting confidence, increasing the complexities of your solutions - for the fun of it - then one day you'll turn around and discover that nobody actually did that one! And that's the way to become a computer scientist.

-- Richard Feynmann, Feynmann Lectures on Computation

I was remined of this thought of Feynmann's while reading the paper

W.J. Fokkink, J.-H. Hoepman, and J. Pang. A note on K-state self-stabilization in a ring with K=N. CWI Report SEN-R0402, 2004.

In that well-written and short paper, the authors study a classic, self-stabilizing mutual exclusion algorithm of Dijkstra's for a collection of some number N of K-state processes organized in a unidirectional ring. This algorithm has been proven to be indeed self-stabilizing if K is larger than N, and claimed to be correct by Dijkstra also under the weaker assumption that K be greater than or equal to N.

Two natural questions that naturally arise are:

1. Can one give a proof that the algorithm is correct if K is equal to N? (This would confirm Dijkstra's claim.)
2. Does the algorithm work if K is smaller than N?

Surprisingly, it seems that the answers to these questions are not given in the literature.

I am happy to say that the authors provide answers to the questions above in their paper by showing that

1. the algorithm also stabilizes when K=N, and
2. this lower bound on the number of states is sharp.

The authors' proof has been checked using PVS.

Indeed, if you keep asking questions about stuff that others have done, getting confidence, increasing the complexities of your solutions - for the fun of it - then one day you'll turn around and discover that nobody actually did that one!