Probabilistic Stabilization under Probabilistic Schedulers (New Trends in Algorithms and Theory of Computation)
Yukiko Yamauchi, Sébastien Tixeuil, Masafumi Yamashita · Institutional Repositories DataBase (IRDB) · 2012
a g g e r 概要 Probabilistically stabilizing systems, which are considered to be a probabilistic version of self- stabilizing systems, guarantee that any execution eventually reaches a legitimate execution with probability 1.Unlike self-stabilizing systems, prob- abilistically stabilizing systems are easy to design, and indeed any weak stabilizing system can be automatically transformed into a probabilistically stabilizing system either by randomizing the algo- rithm or by introducing a probabilistic scheduler, provided that the number of configurations is $fi-$ nite [Devismes et al., 2008].In this paper, we discuss how to design a probability distribution $D$ for a given weak stabilizing algorithm to obtain a good probabilistically stabilizing system under an adversarial probabilistic scheduler $M$ .Our good- ness measure is the convergence time; the expected number of steps $\tau_{D,M}$ necessary to reach a legiti- mate execution from the worst initial configuration.We then show a necessary and sufficient condition for a $D$ to exist such that $\tau_{D,M}<$ oo for any $M$ in a wide and natural class of probabilistic schedulers.