This paper presents the results of a case study involving the use of a formal graphical notation, Modechart, and an automatic verification tool, the Concurrency Workbench, in the analysis of the design of a fault-tolerant active structural control system. Such control systems must satisfy strict requirements on their timing behavior; we show how to use various equivalence-based features supported by the Workbench to examine the timing behavior of different design alternatives, one of which has in excess of 10^19 states. The central insight arising from the study involves the importance of compositionality for reasoning about large and complex systems; in particular, the success of the case study depends integrally on our notation's and tool's support of component-wise minimization.
Despite the enormous strides made in automatic verification technology over the past decade and a half, tools such as model checkers remain relatively underused in the development of software. One reason for this is that the bewildering array of specification and verification formalisms complicates the development and adoption by users of relevant tool support. This paper proposes a remedy to this state of affairs in the case of finite-state concurrent systems by describing an approach to developing customizable yet efficient verification tools.
Note: A journal version subsumes this paper.
This paper develops a temporal process algebra, CSA, for reasoning about distributed systems that involve qualitative timing constraints. It is a conservative extension of Milner's CCS that combines the idea of multiple clocks from the algebra PMC with the assumption of maximal progress familiar from timed process algebras such as TPL. Using a typical class of examples drawn from hardware design, we motivate why these features are useful and in some cases necessary for modeling and verifying distributed systems. We also present fully-abstract behavioral congruences based on the notion of strong bisimulation and observational equivalence, respectively. For temporal strong bisimulation we give sound and complete axiomatizations for several classes of processes.
This paper describes an approach for modeling real-time systems using dynamic priorities. The advantage of the technique is that it drastically reduces the state space sizes of the systems in question while preserving properties of their functional behavior. We demonstrate the utility of our apporach by formally modeling and verifying aspets of the SCSI-2 bus-protocol. It turns out that the state space of this model is about an order of magnitude smaller than the one resulting from traditional real-time semantics.
Note: A journal version subsumes this paper.
The paper has no abstract.
| Go to Rance Cleaveland's publication home page. |
Last modified: April 7, 1999
Rance Cleaveland