Verification of schedulability for real-time programs

Assume that a real-time programP ^T consisting of a number of parallel processes is executed on a system having a setPr of processors which are shared between the processes by a real-time schedulerS ^T. Assume that P^T must meet some timing deadlines. We show that such an implementation ofP ^T can be represented as a transformationL(P ^T) and that the deadlines ofP ^T will be met if they are satisfied by the timing properties of the transformed program. The condition for feasibility of a real-time program executed under a scheduler is formalized and rules are provided for verification. The schedulerS ^T can be specifiedgenerically and applied to different programs, making it unnecessary to introduce low-level operations such as scheduling primitives into the programming language. Thus real-time program specification and Schedulability can be considered in the same framework and the timing properties of a program can be determined at the specification level. By separating the specification of the scheduler from that of the program, the feasibility of an implementation can be proved by considering a scheduling policy rather than its implementation details.     

Automated verification and refinement for physical-layer protocols

This paper demonstrates how to use a satisfiability modulo theories (SMT) solver together with a bounded model checker to verify properties of real-time physical layer protocols. The method is first used to verify the Biphase Mark protocol, a protocol that has been verified numerous times previously, allowing for a comparison of results. The techniques are extended to the 8N1 protocol used in universal asynchronous receiver transmitters. We then demonstrate the use of temporal refinement to link a finite state specification of 8N1 with its real-time implementation. This refinement relationship relieves a significant disadvantage of SMT approaches—their inability to scale to large problems. Finally, capturing the impact of metastability on timing requirements is a key issue in modeling physical-layer protocols. Rather than model metastability directly, a contribution of our models is treating its effect as a constraint on non-determinism.     

Selecting nonlinear model structures for computer control

Many authors have noted the difficulty of developing the models required for nonlinear model predictive control (NMPC) and other nonlinear, model-based control strategies. One reason this task is difficult is that success depends strongly on initially selecting a reasonable structure for this nonlinear model. Unfortunately, this selection is extremely difficult because most of our intuition about structure/behavior relations (e.g., if the step response exhibits overshoot, a model of at least second order is required) is based on experience with relatively low-order linear models and often fails completely when confronted with comparably simple nonlinear models. To help bridge this chasm between nonlinear model behavior and our linear intuition, this paper describes some broad classes of nonlinear model structures, which may be approximately characterized as mildly nonlinear, strongly nonlinear, or of intermediate nonlinearity, depending on the different ways they violate linear intuition. It is hoped that these results will be useful in selecting simple nonlinear model structures for use in model-based control.     

Sojourn-probability-dependent H∞ control for networked switched systems under asynchronous switching

This paper considers H_∞ controller design for a class of networked switched discrete systems under asynchronous switching. The sojourn probability information – the probability of the switched systems staying in each subsystem – is first used to rebuild the networked switched systems. Also, a time-varying lag, depending on both the network-induced delays and switching signals, is taken into consideration between the switching instants of the controllers and systems model. By considering both sojourn probability information and asynchronous switching, a new kind of networked switched system model is proposed, wherein a set of random variables are proposed to describe the sojourn probabilities of the subsystems. Then, stability analysis and H_∞ performance analysis under asynchronous switching are derived. It should be noted that the system performance depends not only on the time-varying lag, but also on the sojourn probabilities. Finally, an example is given to illustrate the effectiveness of the proposed approach.     

Model-driven development of asynchronous message-driven architectures with AsyncAPI

In the Internet-of-Things (IoT) vision, everyday objects evolve into cyber-physical systems. The massive use and deployment of these systems has given place to the Industry 4.0 or Industrial IoT (IIoT). Due to its scalability requirements, IIoT architectures are typically distributed and asynchronous. In this scenario, one of the most widely used paradigms is publish/subscribe, where messages are sent and received based on a set of categories or topics. However, these architectures face interoperability challenges. Consistency in message categories and structure is the key to avoid potential losses of information. Ensuring this consistency requires complex data processing logic both on the publisher and the subscriber sides. In this paper, we present our proposal relying on AsyncAPI to automate the design and implementation of these asynchronous architectures using model-driven techniques for the generation of (part of) message-driven infrastructures. Our proposal offers two different ways of designing the architectures: either graphically, by modeling and annotating the messages that are sent among the different IoT devices, or textually, by implementing an editor compliant with the AsyncAPI specification. We have evaluated our proposal by conducting a set of experiments with 25 subjects with different expertise and background. The experiments show that one-third of the subjects were able to design and implement a working architecture in less than an hour without previous knowledge of our proposal, and an additional one-third estimated that they would only need less than two hours in total.

     

Optimized implementation of synchronous models on industrial LTTA systems

Synchronous models are used to specify embedded systems functions in a clear and unambiguous way and allow verification of properties using formal methods. The implementation of a synchronous specification on a distributed architecture must preserve the model semantics to retain the verification results. Globally synchronized time-triggered architectures offer the simplest implementation path, but can be inefficient or simply unavailable. In past work, we defined a mapping of synchronous models on a general class of distributed asynchronous architectures, for which the only requirement is a lower bound on the rate of activation of tasks. In this paper, we set tighter requirements on task execution rates, and we include a realistic modeling of communication delays, task scheduling delays and schedulability conditions, discussing the timing characteristics of an implementation on a system with a Controller Area Network (CAN). Next, the semantics preservation conditions are formulated as constraints in an architecture optimization problem that defines a feasible task model with respect to timing constraints. An automotive case study shows the applicability of the approach and provides insight on the software design elements that are critical for a feasible implementation.     

Open consensus

This paper presents the abstraction of open consensus and argues for its use as an effective component for building reliable agreement protocols in practical asynchronous systems where processes and links can crash and recover. The specification of open consensus has a decoupled, on‐demand and re‐entrant flavour that make its use very efficient, especially in terms of forced logs, which are known to be major sources of overhead in distributed systems. We illustrate the use of open consensus as a basic building block to develop a modular, yet efficient, total‐order broadcast protocol. Finally, we describe our Java implementation of our open‐consensus abstraction and we convey our efficiency claims through some practical performance measures. Copyright © 2001 John Wiley & Sons, Ltd.     

Generating asynchronous test cases from test purposes

Context

Input/output transition system (IOTS) models are commonly used when next input can arrive even before outputs are produced. The interaction between the tester and an implementation under test (IUT) is usually assumed to be synchronous. However, as the IUT can produce outputs at any moment, the tester should be prepared to accept all outputs from the IUT, or else be able to block (refuse) outputs of the implementation. Testing distributed, remote applications under the assumptions that communication is synchronous and actions can be blocked is unrealistic, since synchronous communication for such applications can only be achieved if special protocols are used. In this context, asynchronous tests can be more appropriate, reflecting the underlying test architecture which includes queues.

Objective

In this paper, we investigate the problem of constructing test cases for given test purposes and specification input/output transition systems, when the communication between the tester and the implementation under test is assumed to be asynchronous, performed via multiple queues.

Method

When issuing verdicts, asynchronous tests should take into account a distortion caused by the queues in the observed interactions. First, we investigate how the test purpose can be transformed to account for this distortion when there are a single input queue and a single output queue. Then, we consider a more general problem, when there may be multiple queues.

Results

We propose an algorithm which constructs a sound test case, by transforming the test purpose prior to composing it with the specification without queues.

Conclusion

The proposed algorithm mitigates the state explosion problem which usually occurs when queues are directly involved in the composition. Experimental results confirm the resulting state space reduction.     

On the Complexity of Verifying Concurrent Transition Systems

In implementation verification, we check that an implementation is correct with respect to a specification by checking whether the behaviors of a transition system that models the program's implementation correlate with the behaviors of a transition system that models its specification. In this paper, we investigate the effect of concurrency on the complexity of implementation verification. We consider trace-based and tree-based approaches to the verification of concurrent transition systems, with and without fairness. Our results show that in almost all cases the complexity of the problem is exponentially harder than that of the sequential case. Thus, as in the model-checking verification methodology, the state-explosion problem cannot be avoided.     

The stability of electric energy markets

Power system markets represented by dynamic equations provide insights into the market behavior which are not available from static models. In particular: (1) markets that are required to balance supply and demand precisely at all times may be unstable if one supplier exhibits economies of scale and will be unstable if two suppliers exhibit this behavior. The instability is characterized by one or more positive eigenvalues. (2) Markets where some energy imbalance is allowed to accumulate can exhibit an instability, depending on the exact values of time constants and delays in the system. (3) Congestion can be helpful from the perspective of stability: a market can become unstable in the eigenvalue sense if congestion is removed. (4) A power system (with stable electromechanical dynamic behavior when considered by itself) and market (by itself stable) can, when analyzed jointly, exhibit unstable behavior. Some of the instabilities alluded here are nothing more than fluctuations in demands and prices. However, fluctuations are likely to require larger security margins, thus greater costs to operate the system.     

Integrating a formal method into a software engineering process with UML and Java

We describe how CSP-OZ, a formal method combining the process algebra CSP with the specification language Object-Z, can be integrated into an object-oriented software engineering process employing the UML as a modelling and Java as an implementation language. The benefit of this integration lies in the rigour of the formal method, which improves the precision of the constructed models and opens up the possibility of (1) verifying properties of models in the early design phases, and (2) checking adherence of implementations to models. The envisaged application area of our approach is the design of distributed reactive systems. To this end, we propose a specific UML profile for reactive systems. The profile contains facilities for modelling components, their interfaces and interconnections via synchronous/broadcast communication, and the overall architecture of a system. The integration with the formal method proceeds by generating a significant part of the CSP-OZ specification from the initially developed UML model. The formal specification is on the one hand the starting point for verifying properties of the model, for instance by using the FDR model checker. On the other hand, it is the basis for generating contracts for the final implementation. Contracts are written in the Java Modeling Language (JML) complemented by CSP_jassda, an assertion language for specifying orderings between method invocations. A set of tools for runtime checking can be used to supervise the adherence of the final Java implementation to the generated contracts. This research was partially supported by the DFG project ForMooS (grants OL 98/3-2 and WE 2290/5-1). C. B. Jones     

Timing analysis of MSC specifications with asynchronous concatenation

Message Sequence Chart (MSC) is a graphical and textual language for describing the interactions between system components, and MSC specifications (MSSs) are a combination of a set of basic MSCs (bMSCs) and a High-level MSC that describes potentially iterating and branching system behavior by specifying the compositions of basic MSCs, which offer an intuitive and visual way of specifying design requirements. With concurrent, timing, and asynchronous properties, MSSs are amenable to errors, and their analysis is important and difficult. This paper deals with timing analysis of MSC specifications with asynchronous concatenation. For an MSC specification, we require that for any loop, its first node be flexible in execution time and its any associated external timing constraint be enforced on the entire loop. Such an MSC specification is called a flexible loop-closed MSC specification (FLMSS). We show that for FLMSSs, the reachability analysis and bounded delay analysis problems can be solved efficiently by linear programming. The solutions have been implemented into our tool TASS and evaluated by experiments.     

Observer‐based H ∞ output tracking control for networked control systems

This paper is concerned with observer‐based H _∞ output tracking control for networked control systems. An observer‐based controller is implemented through a communication network to drive the output of a controlled plant to track the output of a reference model. The inputs of the controlled plant and the observer‐based tracking controller are updated in an asynchronous way because of the effects of network‐induced delays and packet dropouts in the controller‐to‐actuator channel. Taking the asynchronous characteristic into consideration, the resulting closed‐loop system is modeled as a system with two interval time‐varying delays. A Lyapunov–Krasovskii functional, which makes use of information about the lower and upper bounds of the interval time‐varying delays, is constructed to derive a delay‐dependent criterion such that the closed‐loop system has a desired H _∞ tracking performance. Notice that a separation principle cannot be used to design an observer gain and a control gain due to the asynchronous inputs of the plant and the controller. Instead, a novel design algorithm is proposed by applying a particle swarm optimization technique with the feasibility of the stability criterion to search for the minimum H _∞ tracking performance and the corresponding gains. The effectiveness of the proposed method is illustrated by an example. Copyright © 2013 John Wiley & Sons, Ltd.     

Delay-Insensitivity and Semi-Modularity

The study of asynchronous circuit behaviors in the presence of component and wire delays has received a great deal of attention. In this paper, we consider asynchronous circuits whose components can be any non-deterministic sequential machines of the Moore type, and describe a formal model for these circuits and their behaviors under the inertial delay model.We model an asynchronous circuit C by a network N of modules with delays associated with its components and/or wires. We compute the behavior of N assuming arbitrary inertial delays in the modules, and take this behavior to be correct. We define N to be strongly delay-insensitive if its behavior remains correct in the presence of arbitrary stray delays, where correctness is defined through the notion of observational equivalence (or bisimulation), one of the strongest forms of behavioral equivalence. We introduce the notion of quasi semi-modularity, which generalizes Muller's definition of semi-modularity to non-deterministic networks. We prove that a circuit, with all the wire delays taken into account, is strongly delay-intensitive if and only if its behavior is quasi semi-modular.     

The Theta-Model: achieving synchrony without clocks

We present a novel partially synchronous system model, which augments the asynchronous model by a (possibly unknown) bound Θ on the ratio of longest and shortest end-to-end delays of messages simultaneously in transit. An upper bound on those delays need not exist, however, and even Θ may hold only after some unknown global stabilization time. Θ-algorithms are fully message-driven and do not have access to bounded drift local clocks, which makes them particularly suitable for VLSI Systems-on-Chip, for example. In this model, we provide a simulation of (eventually achieved) lock-step rounds, which even works in the presence of Byzantine failures. It follows that most problems in distributed computing have a solution in our model: Using the basic consensus algorithm for partially synchronous systems by Dwork et al. (J ACM 35(2):288–323, 1988), for example, Byzantine consensus can be solved. We also introduce a timing transformation technique that facilitates simple correctness proofs and performance analyses of Θ-algorithms, and provide a detailed relation of the Θ-Model to other partially synchronous system models. Supported by the FWF project Theta (proj. no. P17757-N04) and the BM:vit FIT-IT project DCBA (proj. no. 808198).     

Analysis and verification of real-time systems using quantitative symbolic algorithms

The task of checking if a computer system satisfies its timing specifications is extremely important. These systems are often used in critical applications where failure to meet a deadline can have serious or even fatal consequences. This paper presents an efficient method for performing this verification task. In the proposed method a real-time system is modeled by a state-transition graph represented by binary decision diagrams. Efficient symbolic algorithms exhaustively explore the state space to determine whether the system satisfies a given specification. In addition, our approach computes quantitative timing information such as minimum and maximum time delays between given events. These results provide insight into the behavior of the system and assist in the determination of its temporal correctness. The technique evaluates how well the system works or how seriously it fails, as opposed to only whether it works or not. Based on these techniques a verification tool called Verus has been constructed. It has been used in the verification of several industrial real-time systems such as the robotics system described below. This demonstrates that the method proposed is efficient enough to be used in real-world designs. The examples verified show how the information produced can assist in designing more efficient and reliable real-time systems.     

Exploring alternatives for transition verification

When an implementation under test (IUT) is state-based, and its expected abstract behavior is given in terms of a finite state machine (FSM), a checking sequence generated from a specification FSM and applied to an IUT for testing can provide us with high-level confidence in the correct functional behavior of our implementation. One of the issues here is to generate efficient checking sequences in terms of their lengths. As a major characteristics, a checking sequence must contain all β-sequences for transition verification. In this paper, we discuss the possibility of reducing the lengths of checking sequences by making use of the invertible transitions in the specification FSM to increase the choice of β-sequences to be considered for checking sequence generation. We present a sufficient condition for adopting alternative β-sequences and illustrate typical ways of incorporating these alternative β-sequences into existing methods for checking sequence generation to reduce the lengths. Compared to the direct use of three existing methods, our experiments show that most of the time the saving gained by adopting alternative β-sequences falls in the range of 10–40%.     

Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links

Summary.  We consider agreement and leader election on asynchronous complete networks when the processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this paper is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithm for asynchronous complete networks in which the processors are reliable but some channels may be Byzantine faulty. The algorithm can tolerate up to [n−22] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corresponding algorithms, all the processors in the network will have the same correct vector, where the vector contains the private values of all the processors. Received: May 1994/Accepted: July 1995