In Proceedings of the
2005 International Conference on Dependable Systems and Networks (DSN'05).
Yokohama, Japan, pages 98-107, June 2005.
Keywords:
Dependability Assessment, Intrusion Tolerance, Synchrony Assumptions,
Proactive Recovery, Wormholes.
Fault-tolerant protocols, asynchronous and synchronous alike, make
stationary fault assumptions: only a fraction f of the total n nodes may fail. Whilst a synchronous protocol is expected to have
a bounded execution time, an asynchronous one may execute for an arbitrary amount of time, possibly sufficient for
f+1 nodes to fail. This can compromise the safety of the protocol and ultimately the safety of the system. Recent papers propose
asynchronous protocols that can tolerate any number of faults over the lifetime of the system, provided that at most
f nodes become faulty during a given interval. This is achieved through the so-called proactive recovery, which consists of periodically
rejuvenating the system. Proactive recovery in asynchronous systems, though a major breakthrough, has some limitations which
had not been identified before. In this paper, we introduce a system model expressive enough to represent these problems which
remained in oblivion with the classical models. We introduce the predicate
exhaustion-safe, meaning freedom from exhaustion-failures. Based on it, we predict the extent to which
fault/intrusion-tolerant distributed systems (synchronous and asynchronous) can be made to work correctly. Namely, our model
predicts the impossibility of guaranteeing correct behavior of asynchronous proactive recovery systems as exist today. To prove
our point, we give an example of how these problems impact an existing fault/intrusion-tolerant distributed system, the CODEX system, and having identified the problem, we suggest one
(certainly not the only) way to tackle it.