Brief Announcement: Computing Automatically the Stabilization Time Against the Worst and the Best Schedules
| Autor: | Joffroy Beauquier, Stéphane Messika, Colette Johnen |
|---|---|
| Přispěvatelé: | Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Shlomi Dolev |
| Jazyk: | angličtina |
| Rok vydání: | 2006 |
| Předmět: |
Markov chain
Best worst and average case 0102 computer and information sciences 01 natural sciences Randomized algorithm Reduction (complexity) 010104 statistics & probability Corollary 010201 computation theory & mathematics Convergence (routing) Shortest path problem Markov decision process 0101 mathematics Algorithm ComputingMilieux_MISCELLANEOUS Mathematics |
| Zdroj: | Distributed Computing 20th International Symposium of Distributed Computing, DISC 2006 20th International Symposium of Distributed Computing, DISC 2006, Oct 2006, Stockholm, Sweden. pp.543-547, ⟨10.1007/11864219_40⟩ Lecture Notes in Computer Science ISBN: 9783540446248 DISC |
| DOI: | 10.1007/11864219_40⟩ |
| Popis: | In this paper, we reduce the problem of computing the convergence time for a randomized self-stabilizing algorithm to an instance of the stochastic shortest path problem (SSP). The solution gives us a way to compute automatically the stabilization time against the worst and the best policy. Moreover, a corollary of this reduction ensures that the best and the worst policy for this kind of algorithms are memoryless and deterministic. We apply these results here in a toy example. We just present here the main results, to more details, see [1]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|