Skip to main content

Automated Analysis of Impact of Scheduling on Performance of Self-Stabilizing Protocols.

Publication Type
Year of Publication
2015
Conference/Journal Name
International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Publisher
Springer
Abstract
In a concurrent computing system, a scheduler determines at each time which computing task should execute next. Thus, a scheduler
has tremendous impact on the performance of the tasks that it orchestrates. Analyzing the impact of scheduling in a distributed setting is a challenging task, as it is concerned with subtle dimensions such as geographical distance of processes and the achievable level of parallelism. In this paper, we propose an automated method based on probabilistic verification for analyzing fault recovery time in distributed self-stabilizing protocols. We exhibit the usefulness of our approach through a large set of experiments that demonstrate the impact of different types of scheduling policies on recovery time of different classes of stabilizing protocols, and the practical efficiency of classical self-stabilizing scheduler transformers.