Self-stabilization with Path Algebra

International audienceSelf-stabilizing protocols can resist transient failures and guarantee system recovery in a finite time. We highlight the connexion between the formalism of self-stabilizing distributed systems and the formalism of generalised path algebra and asynchronous iterations with delay. We use the later to prove that a local condition on locally executed algorithm (being a strictly idempotent $r$-operator) ensures self-stabilization of the global system. As a result, a parametrized distributed algorithm applicable to any directed graph topology is proposed, and the function parameter of our algorithm is instantiated to produce distributed algorithms for both fundamental and high level applications. Due to fault resilience properties of our algorithm, the resulting protocols are self-stabilizing at no additional cost