Name
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 computed 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2015.08.001 | Theoretical Computer Science |
Keywords | Field | DocType |
probabilistic algorithms,leader election | Leader election,Computer science,Probabilistic analysis of algorithms,Theoretical computer science,Unsafe environment,Almost surely,Probabilistic logic,Distributed computing,Liveness,Safety property,Finite time | Conference |
Volume | Issue | ISSN |
688 | C | 0304-3975 |
Citations | PageRank | References |
1 | 0.36 | 28 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Karine Altisen | 1 | 165 | 15.03 |
| Stéphane Devismes | 2 | 192 | 25.74 |