A Formal Approach to Protocol Interoperability Testing

Porotocol Interoperability testing is an important means to ensure the interconnection and interoperation between protocol products.In this paper,we proposed a formal approach to protocol interoperability testing based on the operational semantics of Concurrent TTCN.We define Concurrent TTCN‘s operational semantics by using Labeled Transition System,and describe the interoperability test execution and test verdict based on Concurrent TTCN.This approach is very helpful for the formation of formal interoperability testing theory and construction of general interoperability testing system.     

A formal approach to protocol performance testing

This paper proposes a formal approach to protocol performance testing based on the extended concurrent TTCN,To meet the needs of protocol performance testing,concurrent TTCN is extended,and the extended concurrent TTCN‘s operational semantics is defined in terms of Input-Output Labeled Transition System.An architecture design of protocol performance test system is described,and an example of test cases and its test result are given.     

A formal mapping-based approach for distributed schedule coordination on projects

Construction projects involve a large number of participants with overlapping scope of work. Coordination of their activities is usually an iterative manual task undertaken by a general contractor that is often unaware of the detailed constraints of other participants. Project schedules play a key role in this coordination and form the backbone of almost all current approaches to process coordination. However, no single schedule represents the perspective of all participants involved in a project. Rather, each participant keeps in some manner a schedule for its own activities, resulting in multiple schedules that need to be coordinated. The current literature does not support simultaneous reasoning across multiple distributed, overlapping schedules. This paper introduces constructs to formalize the integration of participants’ overlapping schedules that represent the same project tasks, but use a different set breakdown structures and level of detail. Implementation of these constructs allows linking of the master schedule to the other participants’ schedules thereby representing the perspectives of all project participants. This integrated perspective facilitates initial schedule coordination and allows rapid identification of schedule conflicts in response to any schedule changes.     

An optimistic checkpointing and message logging approach for consistent global checkpoint collection in distributed systems

Checkpointing and rollback recovery are widely used techniques for achieving fault-tolerance in distributed systems. In this paper, we present a novel checkpointing algorithm which has the following desirable features: A process can independently initiate consistent global checkpointing by saving its current state, called a tentative checkpoint. Other processes come to know about a consistent global checkpoint initiation through information piggy-backed with the application messages or limited control messages if necessary. When a process comes to know about a new consistent global checkpoint initiation, it takes a tentative checkpoint after processing the message (not before processing the message as in existing communication-induced checkpointing algorithms). After a process takes a tentative checkpoint, it starts logging the messages sent and received in memory. When a process comes to know that every other process has taken a tentative checkpoint corresponding to current consistent global checkpoint initiation, it flushes the tentative checkpoint and the message log to the stable storage. The tentative checkpoints together with the message logs stored in the stable storage form a consistent global checkpoint. Two or more processes can concurrently initiate consistent global checkpointing by taking a new tentative checkpoint; in that case, the tentative checkpoints taken by all these processes will be part of the same consistent global checkpoint. The sequence numbers assigned to checkpoints by a process increase monotonically. Checkpoints with the same sequence number form a consistent global checkpoint. We also present the performance evaluation of our algorithm.     

Integral: Petri-net approach to distributed software development

As the architecture of modern software systems continues to evolve in a distributed fashion, the development of such systems becomes increasingly complex, which requires the integration of more sophisticated specification techniques, tools, and procedures into the conventional methodology. An essential capability of an integrated software development environment is a formal specification method to capture effectively the system's functional requirements as well as its performance requirements. A validation and verification (V&V) system based on a formal specification method is of paramount importance to the development and maintenance of distributed systems.

There has been recent interest in integrating software techniques and tools at the specification level. It is also noted that an effective way of achieving such integration is by using wide-spectrum specification techniques. In view of these points, an integrated V&V system, called Integral, is presented that provides comprehensive and homogeneous analysis capabilities to both specification and testing phases of the life-cycle of distributed software systems. The underlying software model that supports various V&V activities in Integral is primarily based on Petri nets and is intended to be wide spectrum. The ultimate goal of this research is to demonstrate to the software industry, domestic or foreign, the availability and applicability of a new Petri-net-based software development paradigm. Integral is a prototype V&V system to support such a paradigm.     

A self-interested distributed economic model predictive control approach to battery energy storage networks

In this work, a dissipativity based distributed economic model predictive control (DEMPC) approach is developed for the operation of battery energy storage (BES) networks in residential microgrids. With the presence of a microgrid power market (MPM), control of the BES systems is formulated as a self-interested distributed control problem, as individual DEMPC controllers minimize their local economic cost functions based on the price prediction of MPM. Due to the intermittent nature of photovoltaic (PV) power generations and load demands, the DEMPC without proper coordination or constraints may lead to excessive energy trading and price oscillations in MPM. To solve this problem, dissipativity theory with dynamic supply rates is adopted in this paper to deal with the interactions between individual users and the MPM. The microgrid-wide performance requirement of attenuation of the net power fluctuations with respect to time-varying PV generation and demands, is converted into the dissipative trajectory constraints imposed on individual DEMPC controllers. The proposed approach is scalable as it does not require online iterative optimizations across the controller network. A case study is presented to illustrate the proposed method.     

A state-based approach to integration testing based on UML models

Correct functioning of object-oriented software depends upon the successful integration of classes. While individual classes may function correctly, several new faults can arise when these classes are integrated together. In this paper, we present a technique to enhance testing of interactions among modal classes. The technique combines UML collaboration diagrams and statecharts to automatically generate an intermediate test model, called SCOTEM (State COllaboration TEst Model). The SCOTEM is then used to generate valid test paths. We also define various coverage criteria to generate test paths from the SCOTEM model. In order to assess our technique, we have developed a tool and applied it to a case study to investigate its fault detection capability. The results show that the proposed technique effectively detects all the seeded integration faults when complying with the most demanding adequacy criterion and still achieves reasonably good results for less expensive adequacy criteria.     

Traffic-aware stress testing of distributed real-time systems based on UML models using genetic algorithms

This paper presents a model-driven, stress test methodology aimed at increasing chances of discovering faults related to network traffic in distributed real-time systems (DRTS). The technique uses the UML 2.0 model of the distributed system under test, augmented with timing information, and is based on an analysis of the control flow in sequence diagrams. It yields stress test requirements that are made of specific control flow paths along with time values indicating when to trigger them. The technique considers different types of arrival patterns (e.g., periodic) for real-time events (common to DRTSs), and generates test requirements which comply with such timing constraints. Though different variants of our stress testing technique already exist (that stress different aspects of a distributed system), they share a large amount of common concepts and we therefore focus here on one variant that is designed to stress test the system at a time instant when data traffic on a network is maximal. Our technique uses genetic algorithms to find test requirements which lead to maximum possible traffic-aware stress in a system under test. Using a real-world DRTS specification, we design and implement a prototype DRTS and describe, for that particular system, how the stress test cases are derived and executed using our methodology. The stress test results indicate that the technique is significantly more effective at detecting network traffic-related faults when compared to test cases based on an operational profile.     

Using formal specifications to support software testing

Formal specifications become more and more important in the development of software, especially but not only in the area of high integrity system design. In this paper it is demonstrated, how, apart from the specification phase, further benefits may be drawn from formal specifications for checking the implementation against the specification. It is shown how the specification can be used for systematically deriving test input data and for automatically evaluating test results. The approach is illustrated using the specification language Z. The same principles may be applied to other specification languages. The approach allows a high degree of automation, drastically improving productivity and quality of the testing process.     

A practical approach for hybrid distributed MPC

This paper presents a framework to deal with distributed optimization problems composed by binary and continuous variables. Instead of using a mixed integer quadratic programming (MIQP), the approach proposed here transforms the MIQP into a set of quadratic programming's (QP) that are easier to solve. In this way an instance of the controller related to each feasible combination of binary variables is created. The distributed controller performs an iterative process where the set of agents must agree on the value of continuous interconnection variables, while each agent must decide the values of local binary variables. During the iteration procedure the instances are rated according to a performance index and the instances with best performance are selected until the best one is obtained. The proposed methodology is applied to economic optimization of networked microgrids.     

A formal method to real-time protocol interoperability testing

Interoperability testing is an important technique to ensure the quality of implementations of network communication protocol. In the next generation Internet protocol, real-time applications should be supported effectively. However, time constraints were not considered in the related studies of protocol interoperability testing, so existing interoperability testing methods are difficult to be applied in real-time protocol interoperability testing. In this paper, a formal method to real-time protocol interoperability testing is proposed. Firstly, a formal model CMpTIOA （communicating multi-port timed input output automata） is defined to specify the system under test （SUT） in real-time protocol interoperability testing; based on this model, timed interoperability relation is then defined. In order to check this relation, a test generation method is presented to generate a parameterized test behavior tree from SUT model; a mechanism of executability pre-determination is also integrated in the test generation method to alleviate state space explosion problem to some extent. The proposed theory and method are then applied in interoperability testing of IPv6 neighbor discovery protocol to show the feasibility of this method.     

A formal framework for verifying distributed embedded systems based on abstraction methods

This paper presents a formal framework for verifying distributed embedded systems. An embedded system is described as a set of concurrent real time functions which communicate through a network of interconnected switches involving messages queues and routing services.In order to allow requirements verification, such a model is then translated into timed automata. However, the complexity inherent in distributed embedded systems often does not allow to apply model checking techniques. Consequently, the paper presents an abstraction-based verification method which consists in abstracting the communication network by end-to-end timed channels. To prove a given safety property φ requires then (1) to prove a set of proof obligations ensuring the correctness of the abstraction step (i.e. the end-to-end channels correctly abstract the network), and (2) to prove φ at the abstract level. The expected advantage of such a method lies in the ability to overcome the combinatorial explosion frequently met when verifying complex systems. This method is illustrated by an avionic case study.     

A bounded distributed connectivity preserving aggregation strategy with collision avoidance property

This paper presents a bounded connectivity preserving control strategy for the aggregation of multi-agent systems. The problem is investigated for two cases of single-integrator agents and unicycles. Under the proposed control strategy, if two agents are in the connectivity range at some point in time, they will stay connected thereafter. The agents finally aggregate while avoiding collision in such a way that the average of the distances between every pair of neighboring agents is bounded by a pre-specified positive real number, which can be chosen arbitrarily small. The results are developed based on some important characteristics of the positive limit set of the closed-loop system under the proposed control strategy and a fundamental property of convex real functions. The theoretical results are verified by simulation.     

A formal approach to designing delay-insensitive circuits

Summary A method for designing delay-insensitive circuits is presented based on a simple formalism. The communication behavior of a circuit with its environment is specified by a regular expression-like program. Based on formal manipulations this program is then transformed into a delay-insensitive network of basic elements realizing the specified circuit. The notion of delay-insensitivity is concisely formalized. Jo C. Ebergen received his Master's degree in Mathematics from Eindhoven University of Technology in 1983. From 1983 until 1987 he has been working as a researcher at the Centre for Mathematics and Computer Science in Amsterdam in the area of VLSI design. In 1987, he received his Ph.D. degree from Eindhoven University of Technology. Currently, he is assistant professor at the University of Waterloo. His main research interests are programming methodology, parallel computations, and delay-insensitive circuit design. Dr. Ebergen is a member of ACM and EATCS.The research reported in this article was carried out while the author was working at CWI (Centre for Mathematics and Computer Science) in Amsterdam     

Systematic testing and formal verification to validate reactive programs

The use of systematic testing and formal verification in the validation of reactive systems implemented in synchronous languages is illustrated. Systematic testing and formal verification are two techniques for checking the consistency between a program and its specification. The approach to validation is through specification: two system views are developed in addition to the program, a behavioural specification for systematic testing and a logical specification for formal verification. Pursuing both activities, reactive programs can be validated both more efficiently (in terms of costs) and more effectively (in terms of confidence in correctness). This principle is demonstrated here using the well known lift example.     

A formal approach to object-oriented databases

Object-oriented database systems are the focus of current research and development efforts. Yet, there is no commonly accepted object model, nor is it clear whether such a model can be developed. This paper reports on efforts to develop a formal framework that contains most features found in current object oriented database systems. The framework contains two parts. The first is a structural object model, including concepts such as structured objects, identity, and some form of inheritance. For this model, we explain the distinction between values and (abstract) objects, describe a system as a directed graph, and discuss declarative languages. The second part deals with higher-order concepts, such as classes and functions as data, methods, and inheritance. This part is a sketch, and leaves many issues unresolved. Throughout the paper, the emphasis is on logic-oriented modeling.     

Concurrent C: A programming language for distributed multiprocessor systems

Recent advances in hardware technology have made the construction of multiprocessor systems economically feasible. This paper describes a new programming language (Concurrent C) suitable for distributed systems which are networks of loosely connected processors, each with its own local storage. Concurrent C is the extended version of the programming language C, incorporating features for parallel processing and interprocess communications.     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

The Failure Trace Archive: Enabling the comparison of failure measurements and models of distributed systems

With the increasing presence, scale, and complexity of distributed systems, resource failures are becoming an important and practical topic of computer science research. While numerous failure models and failure-aware algorithms exist, their comparison has been hampered by the lack of public failure data sets and data processing tools. To facilitate the design, validation, and comparison of fault-tolerant models and algorithms, we have created the Failure Trace Archive (FTA)—an online, public repository of failure traces collected from diverse parallel and distributed systems. In this work, we first describe the design of the archive, in particular of the standard FTA data format, and the design of a toolbox that facilitates automated analysis of trace data sets. We also discuss the use of the FTA for various current and future purposes. Second, after applying the toolbox to nine failure traces collected from distributed systems used in various application domains (e.g., HPC, Internet operation, and various online applications), we present a comparative analysis of failures in various distributed systems. Our analysis presents various statistical insights and typical statistical modeling results for the availability of individual resources in various distributed systems. The analysis results underline the need for public availability of trace data from different distributed systems. Last, we show how different interpretations of the meaning of failure data can result in different conclusions for failure modeling and job scheduling in distributed systems. Our results for different interpretations show evidence that there may be a need for further revisiting existing failure-aware algorithms, when applied for general rather than for domain-specific distributed systems.