Redundancy allocation problems considering systems with imperfect repairs using multi-objective genetic algorithms and discrete event simulation

This paper considers a multi-objective genetic algorithm (GA) coupled with discrete event simulation to solve redundancy allocation problems in systems subject to imperfect repairs. In the multi-objective formulation, system availability and cost may be maximized and minimized, respectively; the failure-repair processes of system components are modeled by Generalized Renewal Processes. The presented methodology provides a set of compromise solutions that incorporate not only system configurations, but also the number of maintenance teams. The multi-objective GA is validated via examples with analytical solutions and shows its superior performance when compared to a multi-objective Ant Colony algorithm. Moreover, an application example is presented and a return of investment analysis is suggested to aid the decision maker in choosing a solution of the obtained set.     

A fault-tolerant architectural approach for dependable systems

A system's structure enables it to generate its intended behavior from its components' behavior. A well-structured system simplifies relationships among components, which can increase dependability. With software systems, the architecture is an abstraction of the structure. Architectural reasoning about dependability has become increasingly important because emerging applications are increasingly complex. We've developed an architectural approach for effectively representing and analyzing fault-tolerant software systems. The proposed solution relies on exception handling to tolerate faults associated with component and connector failures, architectural mismatches, and configuration faults. Our approach, a specialization of the peer-to-peer architectural style, hides inside the architectural elements the complexities of exception handling and propagation. Our goal is to improve a system's overall reliability and availability by making it tolerant of nonmalicious faults.     

Designing dependable agent systems for mobile wireless networks

A mobile ad hoc network (MANET) is a wireless network of mobile devices-such as PDAs, laptops, cell phones, and other lightweight, easily transportable computing devices-in which each node can act as a router for network traffic rather than relying on fixed networking infrastructure. As mobile computing becomes ubiquitous, MANETS becomes increasingly important. As a design paradigm, multiagent systems (MASs) can help facilitate and coordinate ad hoc-scenarios that might include security personnel, rescue workers, police officers, firefighters, and paramedics. On this network, mobile agents perform critical functions that include delivering messages, monitoring resource usage on constrained mobile devices, assessing network traffic patterns, analyzing host behaviors, and revoking access rights for suspicious hosts and agents. Agents can effectively operate in such environments if they are environment aware - if they can sense and reason about their complex and dynamic environments. Altogether, agents living on a MANET must be network, information, and performance aware. This article fleshes out how we apply this approach to populations of mobile agents on a live MANET.     

Diversity and fault avoidance for dependable replication systems

In the hot-standby replication system, the system cannot process its tasks anymore when all replicated nodes have failed. Thus, the remaining living nodes should be well-protected against failure when parts of replicated nodes have failed. Design faults and system-specific weaknesses may cause chain reactions of common faults on identical replicated nodes in replication systems. These can be alleviated by replicating diverse hardware and software. Going one-step forward, failures on the remaining nodes can be suppressed by predicting and preventing the same fault when it has occurred on a replicated node. In this paper, we propose a fault avoidance scheme which increases system dependability by avoiding common faults on remaining nodes when parts of nodes fail, and analyze the system dependability.     

A fast and efficient digital simulation technique for control systems

The new simulation technique uses a digital compensator in the forward path immediately after the error detector in a typical closed loop system. This compensator contains two parameters which can be tuned to obtain very accurate results. This technique was used on a second order closed loop system with a non linear element in the forward path. The results show great improvement over the substitution methods (Halijak and Tustin). When another compensator was introduced in the feedback path, the results are comparable to the highly accurate T-integrator method.     

Web Services with generic simulation models for discrete event simulation

Today the Internet and the World Wide Web (WWW) are on the cusp of a paradigm shift. Up to now most actions in the WWW are sorts of human–computer interaction, but the introduction of the eXtensible Markup Language (XML) changed the perception. The Internet will be seen as a great space of information and with the use of XML and following technologies like Web Services, Grid Computing and Semantic Web the difference between human–machine interaction and machine–machine interaction vanishes. This work investigates the usefulness of XML in the simulation domain and uses Web Service technology to build the SimASP framework for discrete event simulation (DES).     

The customizable fault/error model for dependable distributed systems

Dependability is a qualitative term referring to a system's ability to meet its service requirements in the presence of faults. The types and number of faults covered by a system play a primary role in determining the level of dependability which that system can potentially provide. Given the variety and multiplicity of fault types, to simplify the design process, the system algorithm design often focuses on specific fault types, resulting in either over-optimistic (all fault permanent) or over-pessimistic (all faults malicious) dependable system designs.A more practical and realistic approach is to recognize that faults of varied severity levels and of differing occurrence probabilities may appear as combinations rather than the assumed single fault type occurrences. The ability to allow the user to select/customize a particular combination of fault types of varied severity characterizes the proposed customizable fault/error model (CFEM). The CFEM organizes diverse fault categories into a cohesive framework by classifying faults according to the effect they have on the required system services rather than by targeting the source of the fault condition. In this paper, we develop (a) the complete framework for the CFEM fault classification, (b) the voting functions applicable under the CFEM, and (c) the fundamental distributed services of consensus and convergence under the CFEM on which dependable distributed functionality can be supported.     

Analytical modelling and simulation of small scale,typical and highly available Beowulf clusters with breakdowns and repairs

Beowulf clusters are very popular because of the high computational power they can provide at reasonably low costs. However, the most pressing issues of today’s cluster solutions are the need for high availability and performance. Cluster systems are clearly prone to failures. Even if cover is provided with some probability c, there would be reconfiguration and/or rebooting delays to resume the operation following a failure. In this paper, the performability modelling of both typical and highly available Beowulf multiprocessor systems is presented. The models developed provide a large degree of flexibility to evaluate the performability of typical and highly available Beowulf cluster systems.     

Formal methods integration for the specification of dependable distributed systems

This paper describes a real-world case study in the specification and analysis of dependable distributed systems. The case study is an automated transport system with safety requirements. In order to manage the complexity of the problem of specifying the dynamic behavior of the whole system, a compositional approach is used, based on the integration of the trace logic of the Communicating Sequential Processes (CSP) theory, and stochastic Petri nets (SPNs). It is argued that the integration of different formal methods is a useful approach in the definition of practical engineering methodologies for the specification, design and analysis of complex dependable distributed systems.     

Parallel discrete event simulation with SIMULA

The area of Discrete Event Simulation (DES) is the least impacted by parallel processing even though most of its applications require tremendous amounts of processing time. The common approach of parallelizing individually special purpose programs leads to very limited improvements in performance. We propose here the parallelization of general DES applications written in SIMULA, as a part of an ongoing project that aims towards developing methodologies and architectures for parallel DES. SIMULA is a general purpose process oriented language whose structure allows the creation of processes which can participate in a quasi-parallel execution according to an interleaved fashion. Problems related to the process interference representation, parallel scheduling and process synchronization are defined and solved. To test and verify the theoretical results the parallel execution of experimental and real DES applications has been simulated. The results show that significant improvement in performance can be expected.     

A software integration approach for designing and assessing dependable embedded systems

Embedded systems increasingly entail complex issues of hardware-software (HW-SW) co-design. As the number and range of SW functional components typically exceed the finite HW resources, a common approach is that of resource sharing (i.e., the deployment of diverse SW functionalities onto the same HW resources). Consequently, to result in a meaningful co-design solution, one needs to factor the issues of processing capability, power, communication bandwidth, precedence relations, real-time deadlines, space, and cost. As SW functions of diverse criticality (e.g. brake control and infotainment functions) get integrated, an explicit integration requirement need is to carefully plan resource sharing such that faults in low-criticality functions do not affect higher-criticality functions.On this background, the main contribution of this paper is a dependability-driven framework that helps to conduct the integration of SW components onto HW resources such that the maintenance of system dependability over integration of diverse criticality components is assured by design.We first develop a clustering strategy for SW components into Fault Containment Modules (FCMs) such that error propagation via interaction is minimized. Subsequently, the rules of composition for FCMs with respect to error propagation are developed. To allocate the resulting FCMs to the existing HW resources we provide several heuristics, each optimizing particular attributes thereof. Further, a framework for assessing the goodness of the achieved HW-SW composition as a dependable embedded system is presented. Two new techniques for quantifying the goodness of the proposed mappings are introduced by examples, both based on a multi-criteria decision theoretic approach.     

Using Ada for discrete event simulation

The process interaction approach is proposed for developing a discrete simulation environment in Ada. The introduction of simulation facilities in Ada not only concerns the classical aspect of model building, but allows a new class of problems to be tackled, that is the testing of correctness of programs intended for real-time applications. In this paper attention is focused on the presentation of the process scheduling in the simulation context and on the definition of standard forms of interactions among processes. Simulation facilities are organized by making use of Ada's structuring concepts.     

Boundedness conditions for relative error in fast simulation of reliability of non-Markovian systems

A general model is considered that describes the functioning of non-Markovian systems. A new method is proposed for fast simulation of failure probability. The method allows obtaining estimates with a bounded relative error under some weak conditions. This method is used to evaluate the reliability of a specific class of systems. Numerical examples are considered. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 63–80, July–August 2006.     

A dynamic rescheduling algorithm for resource management in large scale dependable distributed systems

Scheduling is a key component for performance guarantees in the case of distributed applications running in large scale heterogeneous environments. Another function of the scheduler in such system is the implementation of resilience mechanisms to cope with possible faults. In this case resilience is best approached using dedicated rescheduling mechanisms. The performance of rescheduling is very important in the context of large scale distributed systems and dynamic behavior. The paper proposes a generic rescheduling algorithm. The algorithm can use a wide variety of scheduling heuristics that can be selected by users in advance, depending on the system’s structure. The rescheduling component is designed as a middleware service that aims to increase the dependability of large scale distributed systems. The system was evaluated in a real-world implementation for a Grid system. The proposed approach supports fault tolerance and offers an improved mechanism for resource management. The evaluation of the proposed rescheduling algorithm was performed using modeling and simulation. We present experimental results confirming the performance and capabilities of the proposed rescheduling algorithm.     

Discrete event systems with stochastic processing times

Discrete event dynamic systems are studied in which the underlying algebra is the max-algebra and the coefficients in the system, referring to processing times in practice, are stochastic. The processing times and/or the transportation times within a network show stochastic fluctuations. The restrictions are that the stochastic processing times of the nodes in the network are independent and identically distributed. The asymptotic behavior of the system is investigated, and the average duration of one cycle of the process is calculated. A specific example of the theory is considered. The state space is two-dimensional, and the probability distributions are exponential. It is shown that the process approaches a stationary limit as time proceeds. The case when the probability distributions are discrete is also treated. Several examples are given. Two-dimensional systems and, more generally, finite-dimensional systems are considered     

Scalable,low complexity,and fast greedy scheduling heuristics for highly heterogeneous distributed computing systems

For heterogeneous distributed computing systems, important design issues are scalability and system optimization. Given such systems, it is crucial to develop low computational complexity algorithms to schedule tasks in a manner that exploits the heterogeneity of the resources and applications. In this paper, we report and evaluate three scalable, and fast scheduling heuristics for highly heterogeneous distributed computing systems. We conduct a comprehensive performance evaluation study using simulation. The benchmarking outlines the performance of the schedulers, representing scalability, makespan, flowtime, computational complexity, and memory utilization. The set of experimental results shows that our heuristics perform as good as the traditional approaches, for makespan and flowtime, while featuring lower complexity, lower running time, and lower used memory. The experimental results also detail the various scenarios under which certain algorithms excel and fail.