Name
Abstract | ||
|---|---|---|
Although randomized algorithms have widely been used in distributed computing as a means to tackle impossibility results, it is currently unclear what type of randomization leads to the best performance in such algorithms. This paper proposes three automated techniques to find the probability distribution that achieves minimum average recovery time for an input randomized distributed self-stabilizing protocol without changing the behavior of the algorithm. Our first technique is based on solving symbolic linear algebraic equations in order to identify fastest state reachability in parametric discrete-time Markov chains. The second approach applies parameter synthesis techniques from probabilistic model checking to compute the rational function describing the average recovery time and then uses dedicated solvers to find the optimal parameter valuation. The third approach computes over- and under-approximations of the result for a given parameter region and iteratively refines the regions with minimal recovery time up to the desired precision. The latter approach finds sub-optimal solutions with negligible errors, but it is significantly more scalable in orders of magnitude as compared to the other approaches. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/SRDS.2017.22 | 2017 IEEE 36th Symposium on Reliable Distributed Systems (SRDS) |
Keywords | Field | DocType |
parameter synthesis techniques,probabilistic model,rational function,dedicated solvers,optimal parameter valuation,automated fine tuning,probabilistic self-stabilizing algorithms,randomized algorithms,distributed computing,probability distribution,minimum average recovery time,symbolic linear algebraic equations,fastest state reachability,parametric discrete-time Markov chains | Randomized algorithm,Approximation algorithm,Mathematical optimization,Markov process,Computer science,Markov chain,Algorithm,Probabilistic analysis of algorithms,Parametric statistics,Distributed algorithm,Probabilistic logic,Distributed computing | Conference |
ISSN | ISBN | Citations |
1060-9857 | 978-1-5386-1680-2 | 5 |
PageRank | References | Authors |
0.41 | 15 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Saba Aflaki | 1 | 6 | 0.78 |
| Matthias Volk | 2 | 94 | 6.70 |
| Borzoo Bonakdarpour | 3 | 490 | 45.02 |
| Joost-Pieter Katoen | 4 | 4444 | 289.65 |
| Arne Storjohann | 5 | 391 | 33.19 |