1. On probabilistic snap-stabilization.
- Author
-
Altisen, Karine and Devismes, Stéphane
- Subjects
- *
MESSAGE passing (Computer science) , *COMPUTER network protocols , *COMPUTER security , *COMPUTER algorithms , *COMPUTING platforms - Abstract
In this paper, we introduce probabilistic snap-stabilization . We relax the definition of deterministic snap-stabilization without compromising its safety guarantees. In an unsafe environment, a probabilistically snap-stabilizing algorithm satisfies its safety property immediately after the last fault; whereas its liveness property is only ensured with probability 1. We show that probabilistic snap-stabilization is more expressive than its deterministic counterpart. Indeed, we propose two probabilistic snap-stabilizing algorithms for a problem having no deterministic snap- or self-stabilizing solution: guaranteed service leader election in arbitrary anonymous networks. This problem consists in computing a correct answer to each process that initiates the question “Am I the leader of the network?,” i.e. , (1) processes always compute the same answer to that question and (2) exactly one process computes the answer true . Our solutions being probabilistically snap-stabilizing, the answers are only delivered within an almost surely finite time; however any delivered answer is correct, regardless the arbitrary initial configuration and provided the question has been properly started. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF