Brief announcement: Probabilistic stabilization under probabilistic schedulers

Yukiko Yamauchi, Sébastien Tixeuil, Shuji Kijima, Masafumi Yamashita

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


Motivation. Roughly speaking, a weakly stabilizing system S executed under a probabilistic scheduler ρ is probabilistically self-stabilizing, in the sense that any execution eventually reaches a legitimate execution with probability 1 [1-3]. Here ρ is a set of Markov chains, one of which is selected for S by an adversary to generate as its evolution an infinite activation sequence to execute S. The performance measure is the worst case expected convergence time τ S,M when S is executed under a Markov chain M ∈ ρ. Let τ S,ρ = sup Mερ τ S,M. Then S can be "comfortably" used as a probabilistically self-stabilizing system under ρ only if τ S,ρ < ∞. There are S and ρ such that τ S,ρ = ∞, despite that τ S,M < ∞ for any M ∈ ρ. Somewhat interesting is that, for some S, there is a randomised version S* of S such that τ S*,ρ < ∞, despite that τ S,ρ = ∞, i.e., randomization helps. This motivates a characterization of S that satisfies τ S*,ρ < ∞.

Original languageEnglish
Title of host publicationDistributed Computing - 26th International Symposium, DISC 2012, Proceedings
Number of pages2
Publication statusPublished - 2012
Event26th International Symposium on Distributed Computing, DISC 2012 - Salvador, Brazil
Duration: Oct 16 2012Oct 18 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7611 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other26th International Symposium on Distributed Computing, DISC 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Brief announcement: Probabilistic stabilization under probabilistic schedulers'. Together they form a unique fingerprint.

Cite this