IMDEA Software

Iniciativa IMDEA

Inicio > Eventos > Charlas Invitadas > 2017 > Automated Fine-Tuning of Probabilistic Self-Stabilizing Algorithms
Esta página aún no ha sido traducida. A continuación se muestra la página en inglés.

Borzoo Bonakdarpour

martes 31 de octubre de 2017

10:45am Meeting room 302 (Mountain View), level 3

Borzoo Bonakdarpour, Assistant Research Professor, McMaster University, Canada

Automated Fine-Tuning of Probabilistic Self-Stabilizing Algorithms


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. In this talk, I propose 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.