Dynamic FTSS in asynchronous systems: The case of unison |
| |
Authors: | Swan Dubois Maria Potop-Butucaru Sébastien Tixeuil |
| |
Affiliation: | a UPMC Sorbonne Universités, Franceb INRIA Rocquencourt, Project-Team REGAL, Francec Institut Universitaire de France, France |
| |
Abstract: | Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient faults hit the system. FTSS (Fault-Tolerant Self-Stabilizing) protocols combine the best of both worlds since they tolerate simultaneously transient and (permanent) crash faults. To date, deterministic FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components.In this paper, we present the first study of deterministic FTSS solutions for dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present several impossibility results for this difficult problem and propose an FTSS solution (when the problem is solvable) for the state model that exhibits optimal fault-containment. |
| |
Keywords: | Distributed algorithms Self-stabilization Fault-tolerance Unison Clock synchronization |
本文献已被 ScienceDirect 等数据库收录! |
|