The Worst-Case Stabilization Time of a Self-Stabilizing Algorithm under the Weakly Fair Daemon Model
Authors:
- 1 July 2010
- journal article
- Published by IGI Global Scientific Publishing in International Journal of Artificial Life Research
- Vol. 1 (3) , 45-52
Abstract
In this paper, the result of any self-stabilizing algorithm under the weakly fair daemon model (for a particular problem) that is not self-stabilizing under the non-fair central daemon model is obtained. Also, if any safe configuration under the weakly fair daemon model is also a safe configuration under the non-fair central daemon model, the worst-case stabilization time, measured in steps, is infinity. The implication of this new finding is that any problem, the existence of self-stabilizing algorithms for the weakly fair daemon model only, is unsatisfactory, that is of significance to pursue self-stabilizing algorithms for the non-fair central daemon model.Keywords
This publication has 13 references indexed in Scilit:
- A self-stabilizing algorithm for the shortest path problem assuming the distributed demonComputers & Mathematics with Applications, 2005
- A SILENT SELF-STABILIZING ALGORITHM FOR FINDING CUT-NODES AND BRIDGESParallel Processing Letters, 2005
- A self-stabilizing algorithm for the shortest path problem in a distributed systemComputers & Mathematics with Applications, 2002
- Self-stabilizing depth-first token circulation in arbitrary rooted networksDistributed Computing, 2000
- Self-Stabilization2000
- Distributed resetIEEE Transactions on Computers, 1994
- Self-stabilizing depth-first searchInformation Processing Letters, 1994
- Self-stabilizing depth-first token circulation on networksDistributed Computing, 1993
- Self-stabilization of dynamic systems assuming only read/write atomicityDistributed Computing, 1993
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974