Dynamic FTSS in asynchronous systems: the case of unison (Q551164)

The paper analyzes the protocols for fault-tolerant self-stabilizing in asynchronous systems for dynamic tasks that require safety and liveness properties. In particular, the unison problem is considered, a type of local clock synchronization problem. The authors prove that whenever two or more crash faults may occur, deterministic solutions are impossible in any asynchronous setting. The main contribution of the paper is the characterization of two key properties satisfied by all self-stabilizing asynchronous unison protocols, namely minimality and priority. Moreover, a universal fault-tolerant self-stabilizing protocol is introduced for connected networks of maximum degree at most two. The new protocol satisfies the minimality and priority properties.