TY - GEN
T1 - Brief announcement
T2 - 26th International Symposium on Distributed Computing, DISC 2012
AU - Yamauchi, Yukiko
AU - Tixeuil, Sébastien
AU - Kijima, Shuji
AU - Yamashita, Masafumi
N1 - Funding Information:
This work is supported in part by MEXT/IPSJ KAKENHI (21650002, 22300004, 23700019, 24104003, and 24650008), ANR project SHAMAN and JSPS fellowship.
PY - 2012
Y1 - 2012
N2 - 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*,ρ < ∞.
AB - 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*,ρ < ∞.
UR - http://www.scopus.com/inward/record.url?scp=84868348004&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84868348004&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-33651-5_34
DO - 10.1007/978-3-642-33651-5_34
M3 - Conference contribution
AN - SCOPUS:84868348004
SN - 9783642336508
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 413
EP - 414
BT - Distributed Computing - 26th International Symposium, DISC 2012, Proceedings
Y2 - 16 October 2012 through 18 October 2012
ER -