Model Checking a Fault-Tolerant Startup Algorithm:
From Design Exploration To Exhaustive Fault Simulation

The increasing performance of modern model-checking tools offers high potential for the computer-aided design of fault-tolerant algorithms. Instead of re lying on human imagination to generate taxing failure scenarios to probe a fault-tolerant algorithm during development, we define the fault behavior of a faulty process at its interfaces to the remaining system and use model checking to automatically examine all possible failure scenarios. We call this approach "exhaustive fault simulation". In this paper we illustrate exhaustive fault simulation using a new startup algorithm for the Time-Triggered Architecture (TTA) and show that this approach is fast enough to be deployed in the design loop. We use the SAL toolset from SRI for our experiments and describe an approach to modeling and analyzing fault-tolerant algorithms that exploits the capabilities of tools such as this.

Online Copy

	© 2004 IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
	Paper is available as Postscript (450 KB) or gzip'ed Postscript (162 KB)

BibTeX Entry

@InProceedings{SRSP:DSN04, author = "Wilfried Steiner and John Rushby and Maria Sorea and Holger Pfeifer", title = "{Model Checking a Fault-Tolerant Startup Algorithm: From Design Exploration To Exhaustive Fault Simulation}", year = 2004, booktitle = "Proc. of the 2004 International Conference on Dependable Systems and Networks", pages = "189--198", publisher = "IEEE Computer Society", address = "Florence, Italy", month = jun }