Skip to Main content Skip to Navigation
New interface
Journal articles

Dynamic FTSS in asynchronous systems: The case of unison

Swan Dubois 1 Maria Potop-Butucaru 1 Sébastien Tixeuil 2, 3 
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
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.
Complete list of metadata
Contributor : Swan Dubois Connect in order to contact the contributor
Submitted on : Thursday, September 29, 2011 - 3:19:28 PM
Last modification on : Friday, January 21, 2022 - 3:21:27 AM

Links full text



Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil. Dynamic FTSS in asynchronous systems: The case of unison. Theoretical Computer Science, 2011, 412 (29), pp.3418-3439. ⟨10.1016/j.tcs.2011.02.012⟩. ⟨inria-00627763⟩



Record views