Weak <i>vs</i>. Self <i>vs</i>. Probabilistic Stabilization

作     者：Devismes, Stephane Tixeuil, Sebastien Yamashita, Masafumi 

作者机构：Univ Grenoble 1 VERMA UMR 5104 Grenoble France Univ Paris 06 Sorbonne Univ Paris France IUF Paris France Kyushu Univ Dept Informat Fukuoka Japan 

出 版 物：《INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE》 (国际计算机科学基础杂志)

年 卷 期：2015年第26卷第3期

页      面：293-319页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Distributed systems distributed algorithm fault-tolerance self-stabilization weak stabilization probabilistic self-stabilization 

摘      要：Self-stabilization is a strong property, which guarantees that a distributed system always resumes a correct behavior starting from an arbitrary initial state. Since it is a strong property, some problems cannot have self-stabilizing solutions. Weaker guarantees hence have been later introduced to cope with impossibility results, e.g, probabilistic self stabilization only guarantees probabilistic convergence to a correct, behavior, and weak stabilization only guarantees the possibility of convergence. In this paper, we investigate the relative power of self, probabilistic, and weak stabilization, with respect to the set of problems that can be solved. Weak stabilization is by definition stronger than self stabilization and probabilistic self-stabilization in that precise sense. We first show that weak stabilization allows to solve problems having no self-stabilizing solution. We then show that any finite state deterministic weak stabilizing algorithm to solve a problem under the strongly fair scheduler is always a probabilistic;self-stabilizing algorithm to solve the same problem under the randomized scheduler. Unfortunately, this good property does not hold in general for infinite state algorithms. We however show that for some classes of infinite state algorithms, this property holds. These results hint at more practical use of weak stabilizing algorithms, as they are easier to design and prove their correctness than their self stabilizing and probabilistic self stabilizing counterparts.