A comparison of simulation techniques and algebraic techniques for verifying concurrent systems

Simulation-based assertional techniques and process algebraic techniques are two of the major methods that have been proposed for the verification of concurrent and distributed systems. It is shown how each of these techniques can be applied to the task of verifying systems described as input/output automata; both safety and liveness properties are considered. A small but typical circuit is verified in both of these ways, first using forward simulations, an execution correspondence lemma, and a simple fairness argument, and second using deductions within the process algebra DIOA for I/O automata. An extended evaluation and comparison of the two methods is given.Supported by NSF grant CCR-89-15206, by DARPA contracts N00014-89-J-1988 and N00014-92J-4033, and by ONR contract N00014-91-J-1046.