A Framework for Adaptive Fault-Tolerant Execution of Workflows in the Grid: Empirical and Theoretical Analysis

In this paper, we propose and evaluate a framework for fault tolerant workflow execution in Grid environments. Different from previous work in the literature, our system dynamically chooses an appropriate fault tolerance technique while using a user-defined rule-based system. We also provide a generic interface that can be used to add fault tolerance techniques to the framework. The results obtained with real workflows in an experimental Grid environment show that the overhead introduced by our framework in a failure-free execution is, in the worst evaluated case, approximately 10 %. Moreover, we show that, using our framework, workflows are able to execute successfully in the presence of failures and that the framework can dynamically choose an appropriate fault tolerance technique. The main contributions of our work are twofold: the developed framework and the model-based dependability analysis we performed on it. The purpose in carrying out a model-based dependability analysis consists on evaluating the interaction between our framework and the distributed Grid environment beyond the physical limitations of an empirical evaluation. By doing this, we provide means to plan the assurance of QoS in the Grid resource allocation, while applying the fault-tolerance mechanisms we implement in our framework regardless of the underlying middleware.     

DEVS methodology for evaluating time-constrained message routing policies

Due to its ability to support temporal issues of systems, discrete event simulation is widely applicable to real-time system design. This paper presents a methodology for the modeling and simulation of time-constrained message routing policies for hypercube interconnected real-time systems. The methodology is based on a framework called the DEVS (discrete event systems specification) formalism which supports modular and hierarchical specification of discrete event models. Within the methodology, we first develop DEVS specification for models for hypercube computers and experimental frames to measure the performance of alternative message routing policies. We then implement such specification in DEVSIM++, a C++-based modeling/simulation environment that implements the DEVS formalism. Simulations of various message routing policies are performed, and the performances of such policies are compared.     

Discrete-event modelling of fire spreading

We deal here with the application of discrete-event System Specification (DEVS) formalism to implement a semi-physical fire spread model. Currently, models from physics finely representing forest fires are not efficient and still under development. If current softwares are devoted to the simulation of simple models of fire spread, nowadays there is no environment allowing us to model and simulate complex physical models of fire spread. Simulation models of such a type of models require being easily designed, modified and efficient in terms of execution time. DEVS formalism can be used to deal with these problems. This formalism enables the association of object-oriented hierarchical modelling with discrete-event techniques. Object-oriented hierarchical programming facilitates construction, maintenance and reusability of the simulation model. Discrete-events reduce the calculation domain to the active cells of the propagation domain (the heated ones).     

Distributed simulation of DEVS and Cell-DEVS models in CD++ using Web-Services

Discrete event system specification (DEVS) is a modeling and simulation formalism that has been widely used to study the dynamics of discrete event systems. Cell-DEVS is a DEVS-based formalism that defines spatial models as a cell space assembled of a group of DEVS models connected together. CD++ is a modeling and simulation toolkit capable of executing DEVS and Cell-DEVS models that has proven to be useful for executing complex models. We present the design and implementation of a distributed simulation engine, known as D-CD++, which exposes CD++ simulation utilities as machine-consumable services. In addition, we present the design and implementation of the Web-Service components which enable D-CD++ to expose the simulation functionalities to remote users. Enabling CD++ with Web-Services technology provides a solid framework for interoperating different DEVS implementations in order to achieve a standard DEVS Modeling Language and simulation protocols. This paves the road towards DEVS standardization, while providing a mashup approach, which can lead to higher degree of reuse and reduced time to set up and run experiments, and making sharing among remote users more effective. To prove this fact, we integrate it within larger services (such as a 3D visualization engine), showing the mechanism to incorporate to other environments (including geographical information systems, web-based applications and other modeling and simulation tools) through using standard Web-Service tools. Performance of D-CD++, major bottlenecks and communication overheads are analyzed.     

Model-driven assessment of system dependability

Designers of complex real-time systems need to address dependability requirements early on in the development process. This paper presents a model-based approach that allows developers to analyse the dependability of use cases and to discover more reliable and safe ways of designing the interactions of the system with the environment. The hardware design and the dependability of the hardware to be used also needs to be considered. We use a probabilistic extension of statecharts to formally model the interaction requirements defined in the use cases. The model is then evaluated analytically based on the success and failure probabilities of events. The analysis may lead to further refinement of the use cases by introducing detection and recovery measures to ensure dependable system interaction. A visual modelling environment for our extended statecharts formalism supporting automatic probability analysis has been implemented in AToM³, A Tool for Multi-formalism and Meta-Modelling. Our approach is illustrated with an elevator control system case study.

Model-based evaluation: from dependability to security

The development of techniques for quantitative, model-based evaluation of computer system dependability has a long and rich history. A wide array of model-based evaluation techniques is now available, ranging from combinatorial methods, which are useful for quick, rough-cut analyses, to state-based methods, such as Markov reward models, and detailed, discrete-event simulation. The use of quantitative techniques for security evaluation is much less common, and has typically taken the form of formal analysis of small parts of an overall design, or experimental red team-based approaches. Alone, neither of these approaches is fully satisfactory, and we argue that there is much to be gained through the development of a sound model-based methodology for quantifying the security one can expect from a particular design. In this work, we survey existing model-based techniques for evaluating system dependability, and summarize how they are now being extended to evaluate system security. We find that many techniques from dependability evaluation can be applied in the security domain, but that significant challenges remain, largely due to fundamental differences between the accidental nature of the faults commonly assumed in dependability evaluation, and the intentional, human nature of cyber attacks.     

A synthesis of logic and bio-inspired techniques in the design of dependable systems

Much of the development of model-based design and dependability analysis in the design of dependable systems, including software intensive systems, can be attributed to the application of advances in formal logic and its application to fault forecasting and verification of systems. In parallel, work on bio-inspired technologies has shown potential for the evolutionary design of engineering systems via automated exploration of potentially large design spaces. We have not yet seen the emergence of a design paradigm that effectively combines these two techniques, schematically founded on the two pillars of formal logic and biology, from the early stages of, and throughout, the design lifecycle. Such a design paradigm would apply these techniques synergistically and systematically to enable optimal refinement of new designs which can be driven effectively by dependability requirements. The paper sketches such a model-centric paradigm for the design of dependable systems, presented in the scope of the HiP-HOPS tool and technique, that brings these technologies together to realise their combined potential benefits. The paper begins by identifying current challenges in model-based safety assessment and then overviews the use of meta-heuristics at various stages of the design lifecycle covering topics that span from allocation of dependability requirements, through dependability analysis, to multi-objective optimisation of system architectures and maintenance schedules.     

可信计算及其关键技术研究

The dependability is the latest and highest techno-target used to evaluate the performance quality of a dis-tributed computing system in open network environment, it includes traditional reliability, availability, robustness,survivability, security, data integrity and software protecting ability, etc. A dependable system should not only be provided with fault tolerance ability, but also withstand from risk and recover from disaster, its realization foun dationis the high availability of the information transmission Jaetwork and survivability, fault tolerance and security safe-guard of the system. This paper presents a survey of the survivability mechanisms such as long-distance backup, clus-ter and system recovery, while discussing the techniques of fault tolerance design and information network system se-curity safeguard, and analyzing the information redundant dispersal strategy and model for survivability and security safeguard.     

A modular timed graph transformation language for simulation-based design

We introduce the MoTif (Modular Timed graph transformation) language, which allows one to elegantly model complex control structures for programmed graph transformation. These include modular construction, parallel composition, and a temporal dimension in addition to the usual transformation control structures. The first part of this contribution formally introduces MoTif and its semantics is based on the Discrete EVent system Specification (DEVS) formalism which allows for highly modular, hierarchical modelling of timed, reactive systems. In MoTif, graphs are embedded in events and individual transformation rules are embedded in atomic DEVS models. A side effect of the use of DEVS is the introduction of an explicit notion of time. This allows one to model a time-advance for every rule as well as to interrupt (pre-empt) rule execution. In the second part, we design a case study to show how the explicit notion of time allows for the simulation-based design of reactive systems such as modern computer games. We use the well-known game of PacMan as an example and model its dynamics in MoTif. This also allows the modelling of player behaviour, incorporating data about human players’ behaviour, and reaction times. Thus, a model of both player and game is obtained which can be used to evaluate, through simulation, the playability of a game design. We propose a playability performance measure and change the value of some parameters of the PacMan game. For each variant of the game thus obtained, simulation yields a value for the quality of the game. This allows us to choose an “optimal” (from a playability point of view) game configuration. The user model is subsequently replaced by a visual interface to a real player, and the game model is executed using a real-time DEVS simulator.     

A Real-Time Discrete Event System Specification Formalism for Seamless Real-Time Software Development

We present a time domain extension of the hierarchical and modular discrete event specification (DEVS) formalism. This extension is important for establishing a seamless real-time software development framework. Formalisms help describe a system unambiguously. If formal models are implemented without any consistent frameworks, however, it is hard to guarantee that there is no semantic gap between models and codes. Real-Time DEVS, named RTDEVS, is an extension of DEVS that can be characterized in three perspectives: the real time execution of models, the addition of time interval functions, and the activity specification for each state. After analyzing a system, the framework based on RTDEVS helps to expand each model of the system for executing in a real-time environment. In order to support the RTDEVS formalism, we propose abstract executive concepts based on the abstract simulator concepts of the DEVS formalism. Also, we implement an RTDEVS execution engine, named DEVS Executive, which runs on real-time Mach.     

A location-based fog computing optimization of energy management in smart buildings: DEVS modeling and design of connected objects

Nowadays, smart buildings rely on Internet of things (IoT) technology derived from the cloud and fog computing paradigms to coordinate and collaborate between connected objects. Fog is characterized by low latency with a wider spread and geographically distributed nodes to support mobility, real-time interaction, and location-based services. To provide optimum quality of user life in modern buildings, we rely on a holistic Framework, designed in a way that decreases latency and improves energy saving and services efficiency with different capabilities. Discrete EVent system Specification (DEVS) is a formalism used to describe simulation models in a modular way. In this work, the sub-models of connected objects in the building are accurately and independently designed, and after installing them together, we easily get an integrated model which is subject to the fog computing Framework. Simulation results show that this new approach significantly, improves energy efficiency of buildings and reduces latency. Additionally, with DEVS, we can easily add or remove sub-models to or from the overall model, allowing us to continually improve our designs.     

一种基于中间件的容错系统的研究与设计

随着硬件容错技术的成熟,软件容错技术成为提高系统可靠性的热点问题。直接开发容错应用是非常困难的,鉴于中间件为应用系统提供了良好的开发环境,该文研究和设计了一个基于中间件的容错系统模型,提出了一种新的节点容错结构构造方法,为解决冗余、失效检测和恢复等容错的关键技术问题形成了一套较完整的解决方案。采用马尔科夫过程求出系统的可靠度,验证了系统设计的合理性和可靠性。     

Knowledge-based environment for investigating multicomputer architectures

Multicomputers for massively parallel processing will eventually employ billions of processing elements, each of which will be capable of communicating with every other processing element. A knowledge-based modelling and simulation environment (KBMSE) for investigating such multicomputer architecture at a discrete-event system level is described. The KBMSE implements the discrete-event system specification (DEVS) formalism in an object-oriented programming system of Scheme (a dialect), which supports building models in a hierarchical, modular manner, a systems-oriented approach not possible in conventional simulation languages. The paper presents a framework for knowledge-based modelling and simulation by exemplifying modelling a hypercube multicomputer architecture in the KBMSE. The KBMSE has been tested on a variety of domains characterized by complex, hierarchical structures such as advanced multicomputer architectures, local area computer networks, intelligent multi-robot organizations, and biologically based life-support systems.     

Application-Level Fault Tolerance as a Complement to System-Level Fault Tolerance

As multiprocessor systems become more complex, their reliability will need to increase as well. In this paper we propose a novel technique which is applicable to a wide variety of distributed real-time systems, especially those exhibiting data parallelism. System-level fault tolerance involves reliability techniques incorporated within the system hardware and software whereas application-level fault tolerance involves reliability techniques incorporated within the application software. We assert that, for high reliability, a combination of system-level fault tolerance and application-level fault tolerance works best. In many systems, application-level fault tolerance can be used to bridge the gap when system-level fault tolerance alone does not provide the required reliability. We exemplify this with the RTHT target tracking benchmark and the ABF beamforming benchmark.     

Improving reliability of cooperative concurrent systems with exception flow analysis

Developers of fault-tolerant distributed systems need to guarantee that fault tolerance mechanisms they build are in themselves reliable. Otherwise, these mechanisms might in the end negatively affect overall system dependability, thus defeating the purpose of introducing fault tolerance into the system. To achieve the desired levels of reliability, mechanisms for detecting and handling errors should be developed rigorously or formally. We present an approach to modeling and verifying fault-tolerant distributed systems that use exception handling as the main fault tolerance mechanism. In the proposed approach, a formal model is employed to specify the structure of a system in terms of cooperating participants that handle exceptions in a coordinated manner, and coordinated atomic actions serve as representatives of mechanisms for exception handling in concurrent systems. We validate the approach through two case studies: (i) a system responsible for managing a production cell, and (ii) a medical control system. In both systems, the proposed approach has helped us to uncover design faults in the form of implicit assumptions and omissions in the original specifications.     

An overview of fault tree analysis and its application in model based dependability analysis

Fault Tree Analysis (FTA) is a well-established and well-understood technique, widely used for dependability evaluation of a wide range of systems. Although many extensions of fault trees have been proposed, they suffer from a variety of shortcomings. In particular, even where software tool support exists, these analyses require a lot of manual effort. Over the past two decades, research has focused on simplifying dependability analysis by looking at how we can synthesise dependability information from system models automatically. This has led to the field of model-based dependability analysis (MBDA). Different tools and techniques have been developed as part of MBDA to automate the generation of dependability analysis artefacts such as fault trees. Firstly, this paper reviews the standard fault tree with its limitations. Secondly, different extensions of standard fault trees are reviewed. Thirdly, this paper reviews a number of prominent MBDA techniques where fault trees are used as a means for system dependability analysis and provides an insight into their working mechanism, applicability, strengths and challenges. Finally, the future outlook for MBDA is outlined, which includes the prospect of developing expert and intelligent systems for dependability analysis of complex open systems under the conditions of uncertainty.     

Dependable design technique for system-on-chip

A technique for highly reliable digital design for two FPGAs under a processor control is presented. Two FPGAs are used in a duplex configuration system design, but better dependability parameters are obtained by the combination of totally self-checking blocks based on a parity predictor. Each FPGA can be reconfigured when a SEU fault is detected. This reconfiguration is controlled by a control unit implemented in a processor. Combinational circuit benchmarks have been considered in all our experiments and computations. All our experimental results are obtained from a XILINX FPGA implementation using EDA tools. The dependability model and dependability calculations are presented to document the improved reliability parameters.     

A review of: “FRACTALS EVERYWHERE”, by Michael Barnsley,Academic Press,San Diego,California, USA 1988

The modelling and analysis of multi-component discrete event systems is a challenging research area. Over 30 years, modelling and simulation research of discrete event system specification (DEVS) has been developed with (1) dense-time, (2) the I/O concept, and (3) hierarchical model construction. Nevertheless, DEVS model verification research began relatively recently considering the whole DEVS research history. In the meantime, over 15 years, the automata theory has been developed to cover the dense-time behaviour verification of discrete event systems. Especially, timed automata (TA) has performed the key role in the field.

This paper builds on the research results that have been achieved from both theories of DEVS and TA. Thus contributions of this paper can be seen from each side. From the viewpoint of the DEVS theory, a finite and nondeterministic DEVS has been found as a verifiable class. From the viewpoint of the TA theory, a TA which is modular and hierarchical as well as verifiable, is proposed. To show the results, this paper uses the top down manner in which a general formalism is defined first and then its sub-classes are introduced.