A formal approach for the development of reactive systems

Context

This paper deals with the development and verification of liveness properties on reactive systems using the Event-B method. By considering the limitation of the Event-B method to invariance properties, we propose to apply the language TLA⁺ to verify liveness properties on Event-B models.

Objective

This paper deals with the use of two verification approaches: theorem proving and model-checking, in the construction and verification of safe reactive systems. The theorem prover concerned is part of the Click_n_Prove tool associated to the Event-B method and the model checker is TLC for TLA⁺ models.

Method

To verify liveness properties on Event-B systems, we extend first the expressivity and the semantics of a B model (called temporal B model) to deal with the specification of fairness and eventuality properties. Second, we propose semantics of the extension over traces, in the same spirit as TLA⁺ does. Third, we give verification rules in the axiomatic way of the Event-B method. Finally, we give transformation rules from a temporal B model into a TLA⁺ module. We present in particular, our prototype system called B2TLA⁺, that we have developed to support this transformation; then we can verify liveness properties thanks to the model checker TLC on finite state systems. For the verification of infinite-state systems, we propose the use of the predicate diagrams and its associated tool DIXIT. As the B refinement preserves invariance properties through refinement steps, we propose some rules to get the preservation of liveness properties by the B refinement.

Results

The proposed approach is applied for the development of some reactive systems examples and our prototype system B2TLA⁺ is successfully used to transform a temporal B model into a TLA⁺ module.

Conclusion

The paper successfully defines an approach for the specification and verification of safety and liveness properties for the development of reactive systems using the Event-B method, the language TLA⁺ and the predicate diagrams with their associated tools. The approach is illustrated on a case study of a parcel sorting system.     

Checking Cache-Coherence Protocols with TLA+

We have a great deal of experience using the specification language TLA⁺ and its model checker TLC to analyze protocols designed at Digital and Compaq (both now part of HP). The tools and techniques we have developed apply equally well to software and hardware designs. In this paper, we describe our experience using TLA⁺ and TLC to verify cache-coherence protocols.     

Pointfree expression and calculation: from quantification to temporal logic

Pointfree formulation means suppressing domain variables to focus on higher-level objects (functions, relations). Advantages are algebraic-style calculation and abstraction as formal logics pursue by axiomatization. Various specific uses are considered, starting with quantification in the wider sense (?, ?, ∑, etc.). Pointfree style is achieved by suitable functionals that prove superior to pointwise conventions such as the Eindhoven notation. Pointwise calculations from the literature are reworked in pointfree form. The second use considered is in describing systems, with generic functionals capturing signal flow patterns. An illustration is the mathematics behind a neat magician’s trick, whose implementation allows comparing the pointfree style in Funmath, LabVIEW, TLA⁺, Haskell and Maple. The third use is making temporal logic calculational, with a simple generic Functional Temporal Calculus (FTC) for unification. Specific temporal logics are then captured via endosemantic functions. The example is TLA⁺. Calculation is illustrated by deriving various theorems, most related to liveness issues, and discovering results by calculation rather than proving them afterwards. To conclude, various ramifications, style and abstraction issues are discussed, in relation to engineering mathematics in general and to categorical formulations.     

Fast Paxos

As used in practice, traditional consensus algorithms require three message delays before any process can learn the chosen value. Fast Paxos is an extension of the classic Paxos algorithm that allows the value to be learned in two message delays. How and why the algorithm works are explained informally, and a TLA⁺ specification of the algorithm appears as an appendix.     

Formal specification of a Web services protocol

We describe a use of formal methods to specify and check a Web Services protocol. The Web Services Atomic Transaction protocol was specified in TLA⁺ and checked with the TLC model checker. A modest effort revealed oversights that caused unanticipated behaviors of the protocol; these were corrected by clarifications and changes to the protocol.     

A modal specification theory for components with data

Modal specification is a well-known formalism used as an abstraction theory for transition systems. Modal specifications are transition systems equipped with two types of transitions: must-transitions that are mandatory to any implementation, and may-transitions that are optional. The duality of transitions allows for developing a unique approach for both logical and structural compositions, and eases the step-wise refinement process for building implementations. We propose Modal Specifications with Data (MSDs), the first modal specification theory with explicit representation of data. Our new theory includes the most commonly seen ingredients of a specification theory; that is parallel composition, conjunction and quotient. As MSDs are by nature potentially infinite-state systems, we propose symbolic representations based on effective predicates. Our theory serves as a new abstraction-based formalism for transition systems with data.     

Systematic Design of Systolic Correlators with Application to Parallel Blackman–Tukey Spectral Estimation

Different word-level systolic algorithms exhibiting different properties are derived systematically for the problem of correlation computation by applying certain transformations on the dependence graph which represents the algorithm. The algorithm with properties which best suit the application of Blackman–Tukey spectral estimation is selected and the complete estimator comprising autocorrelation, windowing and DFT computation is implemented systolicly. The overall computation time of the parallel system is 6LT_x+3LT₊ as compared to (3L/2log₂L+2L)T_x+(3Llog₂L)T₊ for the serial system with fast autocorrelation and FFT where L is the number of input data samples and T_x and T₊ are the times needed for one multiplication and one addition respectively. This indicates that the parallel system has a speed advantage over the serial system for L≥16 and this speed advantage increases with L. For a typical 1024-sample segment, the parallel system is almost three times faster. The system is also modified to suit applications where a number of spectrum measurements are required consecutively as is the case with iterative spectral estimators. For the modified system, the system clock period can be made as small as 2T_x+T₊ compared to [(3/2)log₂L+2]T_x+(3log₂L)T₊ for the serial system so that the parallel system can operate at a higher rate for any value of L. Received August 14, 2000     

Specifying and analyzing early requirements in Tropos

We present a framework that supports the formal verification of early requirements specifications. The framework is based on Formal Tropos, a specification language that adopts primitive concepts for modeling early requirements (such as actor, goal, and strategic dependency), along with a rich temporal specification language. We show how existing formal analysis techniques, and in particular model checking, can be adapted for the automatic verification of Formal Tropos specifications. These techniques have been implemented in a tool, called the T-Tool, that maps Formal Tropos specifications into a language that can be handled by the NuSMV model checker. Finally, we evaluate our methodology on a course-exam management case study. Our experiments show that formal analysis reveals gaps and inconsistencies in early requirements specifications that are by no means trivial to discover without the help of formal analysis tools.

A divide-and-conquer direct differentiation approach for multibody system sensitivity analysis

In the design and analysis of multibody dynamics systems, sensitivity analysis is a critical tool for good design decisions. Unless efficient algorithms are used, sensitivity analysis can be computationally expensive, and hence, limited in its efficacy. Traditional direct differentiation methods can be computationally expensive with complexity as large as O(n ⁴+n ² m ²+nm ³), where n is the number of generalized coordinates in the system and m is the number of algebraic constraints. In this paper, a direct differentiation divide-and-conquer approach is presented for efficient sensitivity analysis of multibody systems with general topologies. This approach uses a binary tree structure to traverse the topology of the system and recursively generate the sensitivity data in linear and logarithmic complexities for serial and parallel implementations, respectively. This method works concurrently with the forward dynamics problem, and hence, requires minimal data storage. The differentiation required in this algorithm is minimum as compared to traditional methods, and is generated locally on each body as a preprocessing step. The method provides sensitivity values accurately up to integration tolerance and is insensitive to perturbations in design parameter values. This approach is a good alternative to existing methodologies, as it is fairly simple to implement for general topologies and is computationally efficient.     

Specifications: Formal and informal—a case study

Formal specifications (algebraic) are given for an informally specified small subsystem of the Change Management Automatic Build System. A comparison of the two specifications shows that although informal specifications are easier to read, the formal specifications are clearer, specify operation domains precisely, define the interaction between the operations, show the incompleteness of the informal specifications and are devoid of implementation details. The formal specifications pointed to the need of a function not in the subsystem whose inclusion would improve the system design. This inclusion is now being considered. However, the use of algebraic specifications requires practice and experience. Although the formal specification of large systems is somewhat impractical at the moment, experience in using formal specifications can lead to better informal specifications.     

Efficient symbolic computation of process expressions

This paper describes three optimization techniques for the eb³ process algebra. The optimizations are expressed in a new deterministic operational semantics which is shown to be trace-equivalent to a traditional non-deterministic operational semantics. Internal action transitions are eliminated by an efficient preruntime analysis of the structure of a process expression. Execution environments are used to optimize variable instantiation using lazy evaluation. Non-determinism is eliminated by returning a choice between possible transitions. This new operational semantics is implemented in the eb³pai process algebra interpreter to support the eb³ method. The goal of this method is to automate the development of information systems using, among other mechanisms, efficient symbolic computation of process expressions.     

Parallel algorithms for finding polynomial Roots on OTIS-torus

We present two parallel algorithms for finding all the roots of an N-degree polynomial equation on an efficient model of Optoelectronic Transpose Interconnection System (OTIS), called OTIS-2D torus. The parallel algorithms are based on the iterative schemes of Durand–Kerner and Ehrlich methods. We show that the algorithm for the Durand–Kerner method requires (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves using N processors. The parallel algorithm for Ehrlich method is shown to run in (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves with the same number of processors. The algorithms have lower AT cost than the algorithms presented in Jana (Parallel Comput 32:301–312, 2006). The scalability of the algorithms is also discussed.     

Verifying task-based specifications in conceptual graphs

A conceptual model is a model of real world concepts and application domains as perceived by users and developers. It helps developers investigate and represent the semantics of the problem domain, as well as communicate among themselves and with users. In this paper, we propose the use of task-based specifications in conceptual graphs (TBCG) to construct and verify a conceptual model. Task-based specification methodology is used to serve as the mechanism to structure the knowledge captured in the conceptual model; whereas conceptual graphs are adopted as the formalism to express task-based specifications and to provide a reasoning capability for the purpose of verification. Verifying a conceptual model is performed on model specifications of a task through constraints satisfaction and relaxation techniques, and on process specifications of the task based on operators and rules of inference inherited in conceptual graphs.     

Architectural Specifications in CASL

One of the most novel features of CASL, the Common Algebraic Specification Language, is the provision of so-called architectural specifications for describing the modular structure of software systems. A brief discussion of refinement of CASL specifications provides the setting for a presentation of the rationale behind architectural specifications. This is followed by some details of the features provided in CASL for architectural specifications, hints concerning their semantics, and simple results justifying their usefulness in the development process. Received October 2000 / Accepted in revised form July 2001     

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

Effects of the central potassium ions on the G-quadruplex and stabilizer binding

Human telomeres undertake the structure of intra-molecular parallel G-quadruplex in the presence of K⁺ in eukaryotic cell. Stabilization of the telomere G-quadruplex represents a potential strategy to prevent telomere lengthening by telomerase in cancer therapy. Current work demonstrates that the binding of central K⁺ with the parallel G-quadruplex is a coordinated water directed step-wise process. The K⁺ above the top G-tetrad is prone to leak into environment and the 5′-adenine quickly flips over the top G-tetrad, leading to the bottom gate of G-tetrads as the only viable pathway of K⁺ binding. Present molecular dynamics studies on the two most potent stabilizers RHPS4 and BRACO-19 reveal that the central K⁺ has little influence on the binding conformations of the bound stabilizers. But without the central K⁺, either RHPS4 or BRACO-19 cannot stabilize the structure of G-quadruplex. The binding strength of stabilizers evaluated by the MM-PBSA method follows the order of BRACO-19> RHPS4, which agrees with the experimental results. The difference in binding affinities between RHPS4 and BRACO-19 is probably related to the ability to form intramolecular hydrogen bonds and favorable van del Waals interactions with G-quadruplex. In the models that have one central K⁺ located at the upper/lower binding site, the corresponding top/bottom stacked stabilizers show more favorable binding affinities, indicating the apparent promoting effect of central K⁺ on the stabilizer binding. Our findings provide further insights into the regulatory effect of K⁺ on the G-quadruplex targeted binding, which is meaningful to the development of G-quadruplex stabilizers.     

High luminance and high see‐through head‐mounted displays with beam‐splitter‐array waveguides

We have developed head‐mounted displays with high transmittance and luminance, which could be utilized outside safely without dimming glasses. We first specified required optical performance specifications by considering user's safety and usability. In order to ensure that the user is able to recognize both surrounding environment and the image of the head‐mounted display, we set the target specification that the transmittance is higher than or equal to 85%, and the luminance contrast ratio is larger than or equal to 1.15 with display image of white solid pattern. We then developed the beam‐splitter‐array waveguide to achieve the requirements. It has advantages in high efficiency and high see‐through property. In order to determine configuration of the waveguide, we have performed optical ray trace simulation. We also established versatile waveguide measurement method applicable to different‐type waveguides. By utilizing the waveguide we have developed, we made a prototype of a head‐mounted display (HMD) with high transmittance 94% and high luminance 4.8 × 10³ cd/m² and thus luminance contrast ratio 1.25 under the sun. With these advantages, our HMD is suitable for usage outside including applications of work support systems where dimming effect is not preferred, and the HMD is used under the sun.