Fault-tolerance and self-stabilization: impossibility results and solutions using self-stabilizing failure detectors

This paper focuses on protocols that are simultaneously resilient to permanent failures (crash faults) and transient failures (memory and message corruption). First, we show that asynchronous round-based and fault-tolerant protocols cannot be transformed into protocols that are simultaneously fault-tolerant and self-stabilizing (ftss), as is otherwise possible in the synchronous mode of computation. Secondly, we show that it is impossible to find the number of processes (i.e. the size) on a family of networks, as it has been proven for the ring network. Finally, we present a ftss protocol for solving ring size by assuming that each process accesses a failure detector. We also propose two self-stabilizing implementations for the failure detector that differ in their degree of tolerance to transient failures.