Characterizing Fault-Tolerant Systems by Means of Simulation Relations

RAMIRO DEMASI; PABLO F. CASTRO; T.S.E. MAIBAUM; NAZARENO AGUIRRE

LECTURE NOTES IN COMPUTER SCIENCE

Springer

Año: 2013 vol. 7940 p. 428 - 442

0302-9743

In this paper, we study a formal characterization of fault-tolerant behaviors of systems via simulation relations. This formalization makes use of particular notions of simulation and bisimulation in order to compare the executions of a system that exhibit faults with executions where no faults occur. By employing variations of standard (bi)simulation algorithms, our characterization enables us to algorithmically check fault-tolerance, i.e., to verify that a system behaves in an acceptable way even under the occurrence of faults. Our approach has the benefit of being simple and supporting an efficient automated treatment. We demonstrate the practical application of our formalization through some well-known case studies, which illustrate that the main ideas behind most fault-tolerance mechanisms are naturally captured in our setting.