https://www.mdu.se/

Critical systems often use N-modular redundancy to tolerate faults in subsystems. Traditional approaches to N-modular redundancy in distributed, loosely-synchronised, real-time systems handle time and value errors separately: a voter detects value errors, while watchdog-based health monitoring detects timing errors. In prior work, we proposed the integrated Voting on Time and Value (VTV) strategy, which allows both timing and value errors to be detected simultaneously. In this paper, we show how VTV can be harnessed as part of an overall fault tolerance strategy and evaluate its performance using a well-known control application, the Inverted Pendulum. Through extensive simulations, we compare the performance of Inverted Pendulum systems which employs VTV and alternative voting strategies to demonstrate that VTV better tolerates well-recognised faults in this realistically complex control problem.

In dependable embedded real-time systems, typically built of computing nodes exchanging messages over reliability-constrained networks, the provision of schedulability guarantees for task and message sets under realistic fault and error assumptions is an essential requirement, though complex and tricky to achieve. An important factor to be considered in this context is the random nature of occurrences of faults and errors, which, if addressed in the traditional schedulability analysis by assuming a rigid worst-case occurrence scenario, may lead to inaccurate results. In this work we propose a framework for end-to-end probabilistic schedulability analysis for real-time tasks exchanging messages over Controller Area Network under stochastic errors.

Ubiquitous deployment of embedded systems is having a substantial impact on our society, since they interact with our lives in many critical real-time applications. Typically, embedded systems used in safety or mission critical applications (e.g., aerospace, avionics, automotive or nuclear domains) work in harsh environments where they are exposed to frequent transient faults such as power supply jitter, network noise and radiation. They are also susceptible to errors originating from design and production faults. Hence, they have the design objective to maintain the properties of timeliness and functional correctness even under error occurrences.

Fault-tolerance plays a crucial role towards achieving dependability, and the fundamental requirement for the design of effective and efficient fault-tolerance mechanisms is a realistic and applicable model of potential faults and their manifestations. An important factor to be considered in this context is the random nature of faults and errors, which, if addressed in the timing analysis by assuming a rigid worst-case occurrence scenario, may lead to inaccurate results. It is also important that the power, weight, space and cost constraints of embedded systems are addressed by efficiently using the available resources for fault-tolerance.

This thesis presents a framework for designing predictably dependable embedded real-time systems by jointly addressing the timeliness and the reliability properties. It proposes a spectrum of fault-tolerance strategies particularly targeting embedded real-time systems. Efficient resource usage is attained by considering the diverse criticality levels of the systems' building blocks. The fault-tolerance strategies are complemented with the proposed probabilistic schedulability analysis techniques, which are based on a comprehensive stochastic fault and error model.

Dependable real-time embedded systems are typically composed of a number of heterogeneous computing nodes, heterogeneous networks that connect them and tasks with multiple criticality levels allocated to the nodes. The heterogeneous nature of the hardware, results in a varying vulnerability to different types of hardware failures. For example, a computing node with effective shielding shows higher resistance to transient failures caused by environmental conditions such as radiation or temperature changes than an unshielded node. Similarly, resistance to permanent failures can vary depending on the manufacturing procedures used. Vulnerability to different types of errors of a task which may lead to a system failure, depends on several factors, such as the hardware on which the task runs and communicates, the software architecture and the implementation quality of the software, and varies from task to task. This variance, as well as the different criticality levels and real-time requirements of tasks, necessitate novel fault-tolerance approaches to be developed and used, in order to meet the stringent dependability requirements of resource-constrained real-time systems.

In this thesis, the major contribution is four-fold. Firstly, we describe an error classification for real-time embedded systems and address error propagation aspects. The goal of this work is to perform the analysis on a given system, in order to find bottlenecks in satisfying dependability requirements and to provide guidelines on the usage of appropriate error detection and fault tolerance mechanisms.

Secondly, we present a time-redundancy approach to provide a priori guarantees in fixed-priority scheduling (FPS) such that the system will be able to tolerate one value error per every critical task instance by re-execution of every critical task instance or execution of alternate tasks before deadlines, while keeping the associated costs minimized.

Our third contribution is a new approach, Voting on Time and Value (VTV) which extends the N-modular redundancy approach by explicitly considering both value and timing errors, such that correct value is produced at a correct time, under specified assumptions. We illustrate our voting approach by instantiating it in the context of the well-known triple modular redundancy (TMR) approach. Further, we present a generalized voting algorithm targeting NMR that enables a high degree of customization from the user perspective.

Finally, we propose a novel cascading redundancy approach within a generic fault tolerant scheduling framework. The proposed approach is capable of tolerating errors with a wider coverage (with respect to error frequency and error types) than our proposed time and space redundancy approaches in isolation, allows tasks with mixed criticality levels, is independent of the scheduling technique and, above all, ensures that every critical task instance can be feasibly replicated in both time and/or space. The fault-tolerance techniques presented in this thesis address various different error scenarios that can be observed in real-time embedded systems with respect to the types of errors and frequency of occurrence, and can be used to achieve the ultra-high levels of dependability which is required in many critical systems.

In this paper, we present a general framework which allows the designer to specify a wide range of criteria for allocation. Major factors considered as part of our framework are mixed criticalities of tasks, schedulability, power consumption, fault-tolerance, and dependability requirements in addition to typical functional aspects such as memory constraints. This being a global optimization problem, we are forced to use meta-heuristic algorithms, and we were able to represent these requirements in a very intuitive manner by the usage of energy functions in simulated annealing. We envision the proposed methodology as a quite simple, scalable, as well as computationally effective solution covering a wide range of system architectures and solution spaces. 

Dependable communications is becoming a critical factor due to the pervasive usage of networked embedded systems that increasingly interact with human lives in one way or the other in many real-time applications. Though many smaller systems are providing dependable services employing uniprocesssor solutions, stringent fault containment strategies etc., these practices are fast becoming inadequate due to the prominence of COTS in hardware and component based development(CBD) in software as well as the increased focus on building 'system of systems'. Hence the repertoire of design paradigms, methods and tools available to the developers of distributed real-time systems needs to be enhanced in multiple directions and dimensions. In future scenarios, potentially a network needs to cater to messages of multiple criticality levels (and hence varied redundancy requirements) and scheduling them in a fault tolerant manner becomes an important research issue. We address this problem in the context of Controller Area Network (CAN), which is widely used in automotive and automation domains, and describe a methodology which enables the provision of appropriate scheduling guarantees. The proposed approach involves definition of fault-tolerant windows of execution for critical messages and the derivation of message priorities based on earliest deadline first (EDF).

Real-time systems typically have to satisfy complex requirements mapped to the timing attributes of the tasks that are eventually guaranteed by the underlying scheduler. These systems consist of a mix of hard and soft tasks with varying criticalities as well as associated fault tolerance (FT) requirements. Often time redundancy techniques are preferred in many embedded applications and hence it is extremely important to devise appropriate methodologies for scheduling real-time tasks under fault assumptions. Additionally, the relative criticality of tasks could undergo changes during the evolution of the system. Hence scheduling decisions under fault assumptions have to reflect all these important factors in addition to the resource constraints.

In this paper we propose a framework for 'FTfeasibility', i.e., to provide a priori guarantees that all critical tasks in the system will meet their deadlines even in case of faults. Our main objective here is to ensure FTfeasibility of all critical tasks in the system and do so with minimal costs and without any fundamental changes in the scheduling paradigm. We demonstrate its applicability in scenarios where the FT strategy employed is re-execution of the affected tasks or an alternate action upon occurrence of transient faults or software design faults. We analyse a feasible set of tasks and propose methods to adapt it to varying FT requirements without modifications to the underlying scheduler. We do so by reassigning task attributes to achieve FT-feasibility while keeping the costs minimised.

In dependable real-time systems, provision of schedulability guarantees for task sets under realistic fault and error assumptions is an essential requirement, though complex and tricky to achieve. An important factor to be considered in this context is the random nature of occurrences of faults and errors, which, if addressed in the traditional schedulability analysis by assuming a rigid worst case occurrence scenario, may lead to inaccurate results. In this paper we first propose a stochastic fault and error model which has the capability of modeling error bursts in lieu of the commonly used simplistic error assumptions in processor scheduling. We then present a novel schedulability analysis that accounts for a range of worst case scenarios generated by stochastic error burst occurrences on the response times of tasks scheduled under the fixed priority scheduling (FPS) policy. Finally, we describe a methodology for the calculation of probabilistic schedulability guarantees as a weighted sum of the conditional probabilities of schedulability under specified error burst characteristics.

Dependable real-time systems typically consist of tasks of mixed-criticality levels with associated fault tolerance (FT) requirements and scheduling them in a fault-tolerant manner to efficiently satisfy these requirements is a challenging problem. From the designers' perspective, the most natural way to specify the task criticalities is by expressing the reliability requirements at task level, without having to deal with low level decisions, such as deciding on which FT method to use, where in the system to implement the FT and the amount of resources to be dedicated to the FT mechanism. Hence, it is extremely important to devise methods for translating the highlevel requirement specifications for each task into the low-level scheduling decisions needed for the FT mechanism to function efficiently and correctly. In this paper, we focus achieving FT by redundancy in the temporal domain, as it is the commonly preferred method in embedded applications to recover from transient and intermittent errors, mainly due to its relatively low cost and ease of implementation. We propose a method which allows the system designer to specify task-level reliability requirements and provides a priori probabilistic scheduling guarantees for real-time tasks with mixed-criticality levels in the context of preemptive fixed-priority scheduling. We illustrate the method on a running example.

Hard real-time applications typically have to satisfy high dependability requirements in terms of fault tolerance in both the value and the time domains. Loosely synchronized real-time systems, which represent many of the systems that are developed, make any form of voting difficult as each replica may provide different outputs independent of whether there has been an error or not. This can also lead to false positives and false negatives which makes achieving fault tolerance, and hence dependability, difficult. We have earlier proposed a majority voting technique, ”Voting on Time and Value” (VTV) that explicitly considers combinations of value and timing errors, targeting loosely synchronised systems. In this paper, we extend VTV to enable voter parameter tuning to obtain the desired user specified trade-offs between the false positive and false negative rates in the voter outputs. We evaluate the performance of VTV against Compare Majority Voting (CMV), which is a known voting approach applicable in similar contexts, through extensive simulation studies. The results clearly demonstrate that VTV outperforms CMV in all scenarios with lower false negative rates.

The fundamental requirement for the design of effective and efficient fault-tolerance mechanisms in dependable real-time systems is a realistic and applicable model of potential faults, their manifestations and consequences. Fault and error models also need to be evolved based on the characteristics of the operational environments or even based on technological advances. In this paper we propose a probabilistic burst error model in lieu of the commonly used simplistic fault assumptions in the context of processor scheduling. We present a novel schedulability analysis that accounts for the worst case interference caused by error bursts on the response times of tasks scheduled under the fixed priority scheduling (FPS) policy. Further, we describe a methodology for the calculation of probabilistic schedulability guarantees as a weighted sum of the conditional probabilities of schedulability under specified error burst characteristics. Finally, we identify potential sources of pessimism in the worst case response time calculations and discuss potential means for circumventing these issues.

Networked embedded systems used in many real-time (RT) applications rely on dependable communication. Controller Area Network (CAN) has gained wider acceptance as a standard in a large number of applications, mostly due to its cost effectiveness, predictable performance, and its fault-tolerance capability. Research so far has focused on rather simplistic error models which assume only singleton errors separated by a minimum inter-arrival time. However, these systems are often subject to faults that manifest as error bursts of various lengths which have an adverse effect on the message response times that needs to be accounted for. Furthermore, an important factor to be considered in this context is the random nature of occurrences of faults and errors, which, if addressed in the traditional schedulability analysis by assuming a rigid worst case occurrence scenario, may lead to inaccurate results. In this paper we first present a stochastic fault and error model which has the capability of modeling error bursts in lieu of the commonly used simplistic error assumptions. We then present a methodology which enables the provision of appropriate probabilistic RT guarantees in distributed RT systems for the particular case of message scheduling on CAN under the assumed error assumptions

The fundamental requirement for the design of effective and efficient fault-tolerance mechanisms in dependable real-time systems is a realistic and applicable model of potential faults, their manifestations and consequences. Fault and error models also need to be evolved based on the changes in the environments of usage or even based on technological advances. In this paper we propose a novel probabilistic burst error model in lieu of the commonly used simplistic fault assumptions. We introduce an approach to reason about real-time systems schedulability under the proposed error model in a probabilistic manner. We first present a sufficient analysis that accounts for the worst case interference caused by error bursts on the response times of tasks scheduled under the fixed priority scheduling (FPS) policy. Further, we identify potential sources of pessimism in the calculations and propose an algorithm that refines the results.

Dependable real-time systems typically consist of tasks of multiple criticality levels and scheduling them in a fault-tolerantmanner is a challenging problem. Redundancy in the physical and temporal domains for achieving fault tolerance has been often dealt independently based on the types of errors one needs to tolerate. To our knowledge, there had been no work which tries to integrate fault tolerant scheduling and multiple redundancy mechanisms. In this paper we propose a novel cascading redundancy approach within a generic fault tolerant scheduling framework. The proposed approach is capable of tolerating errors with a wider coverage (with respect to error frequency and error types) than time and space redundancy in isolation, allows tasks with mixed criticality levels, is independent of the scheduling technique and, above all, ensures that every critical task instance can be feasibly replicated in both time and space. 

Component-Based Development (CBD) of software, with its successes in enterprise computing, has the promise of being a good development model due to its cost effectiveness and potential for achieving high quality of components by virtue of reuse. However, for systems with dependability concerns, such as real-time systems, a major challenge in using CBD consists of predicting dependability attributes, or providing dependability assertions, based on the individual component properties and architectural aspects. In this paper, we propose a framework which aims to address this challenge. Specifically, we present a revised error classification together with error propagation aspects, and briefly sketch how to compose errormodels within the context of Component-Based Systems (CBS). The ultimate goal is to perform the analysis on a given CBS, in order to find bottle-necks in achieving dependability requirements and to provide guidelines to the designer on the usage of appropriate error detection and fault tolerance mechanisms.

Real-time applications typically have to satisfy high dependability requirements and require fault tolerance in both value and time domains. A widely used approach to ensure fault tolerance in dependable systems is the N-modular redundancy (NMR) which typically uses a majority voting mechanism. However, NMR primarily focuses on producing the correct value, without taking into account the time dimension. In this paper, we propose a new approach, Voting on Time and Value (VTV), applicable to real-time systems, which extends the modular redundancy approach by explicitly considering both value and timing failures, such that correct value is produced at a correct time, under specified assumptions. We illustrate our voting approach by instantiating it in the context of the well-known triple modular redundancy (TMR) approach. Further, we present a generalized version targeting NMR that enables a high degree of customization from the user perspective.

Dependable communication is becoming a critical factor due to the pervasive usage of networked embedded systems that increasingly interact with human lives in many real-time applications. Controller Area Network (CAN) has gained wider acceptance as a standard in a large number of industrial applications, mostly due to its efficient bandwidth utilization, ability to provide real-time guarantees, as well as its fault-tolerant capability. However, the native CAN fault-tolerant mechanism assumes that all messages transmitted on the bus are equally critical, which has an adverse impact on the message latencies, results in the inability to meet user defined reliability requirements, and, in some cases, even leads to violation of timing requirements. As the network potentially needs to cater to messages of multiple criticality levels (and hence varied redundancy requirements), scheduling them in an efficient fault-tolerant manner becomes an important research issue. We propose a methodology which enables the provision of appropriate guarantees in CAN scheduling of messages with mixed criticalities. The proposed approach involves definition of fault-tolerant feasibility windows of execution for critical messages, and off-line derivation of optimal message priorities that fulfill the user specified level of fault-tolerance.

Real-time systems typically have to satisfy complex requirements, mapped to the task attributes, eventually guaranteed by the underlying scheduler. These systems consist of a mix of hard and soft tasks with varying criticality as well as associated fault tolerance requirements. Additionally, the relative criticality of tasks could undergo changes during the evolution of the system. Time redundancy techniques are often preferred in many embedded applications and, hence, it is extremely important to devise appropriate methodologies for scheduling real-time tasks under error assumptions. In this paper, we propose a methodology to provide a priori guarantees in fixed priority scheduling (FPS) such that the system will be able to tolerate one error per every critical task instance. We do so by using Integer Linear Programming (ILP) to derive task attributes that guarantee re-execution of every critical task instance before its deadline, while keeping the associated costs minimized. We illustrate the effectiveness of our approach, in comparison with fault tolerant (FT) adaptations of the well-known rate monotonic (RM), by simulations.

Embedded systems design, configuration, deployment and runtime management are extremely challenging. The pervasiveness of embedded systems, and their increasing parallelism and scale in number of networked and interacting hardwaresoftware components, has been coupled with increases in the number of functions and the variation in behaviour and characteristics of these functions. Adoption of new international safety standards and higher best practice levels in large manufacturer subcontracting policies however mandates strict quality and at times even stricter dependability and sustainability (in particular energy efficiency) requirements. In recent work we have extended our rich architecture definition language (RADL) and underlying theory to meet such industrial requirements. In this paper we describe a new approach and design model targeting hybrid designer- and operator-defined performance budgets for timing and energy consumption. We give a running example designing a sample embedded multi-media system, a modern digital camera. The model caters for true parallelism, probabilistic performance characterisation, parameterised architectural variation, compositionality, and runtime reconfiguration. The theory is based on hybrid, hierarchical, performance-annotated parallel automata and Petri nets. We also briefly summarise our tool set used to derive the example.

This paper proposes an efficient way to handle fault in controller area network (CAN)-based networked control system (NCS). A fault in a bus line of CAN will induce a data error which will result in data dropout or time delay, and subsequently may lead to performance degradation or system instability. A strategy to handle fault occurrence in CAN bus is proposed to properly analyze the effect of the fault to CAN-based NCS performance. The fault occurrences are modeled based on fault interarrival time, fault bursts' duration, and Poisson law. Using fault and messages' attributes, response time analysis (RTA) is performed and the probability of control message missing its deadline is calculated. Utilizing the new error handling algorithm to replace the native error handling of CAN, the probability of a control message missing its deadline can be translated into the probability of data dropout for control message. This methodology is evaluated using steer-by-wire system of vehicle to analyze the effect of fault occurrences in CAN. It is found that the proposed error handling mechanism has resulted in better NCS performance and the range of data dropout probability for control message also could be obtained, which serves as crucial input for NCS controller design.

Industrial real-time systems typically have to satisfy complex requirements, mapped to the task attributes, eventually guaranteed by a fixed priority scheduler in a distributed environment. These systems consist of a mix of hard and soft tasks with varying criticality, as well as associated fault tolerance requirements. Time redundancy techniques are often preferred in industrial applications and, hence, it is extremely important to devise resource efficient methodologies for scheduling real-time tasks under failure assumptions. In this paper, we propose a methodology to provide a priori guarantees in distributed real-time systems with redundancy requirements. We do so by identifying temporal feasibility windows for all task executions and re-executions, as well as allocating them on different processing nodes. We then use optimization theory to derive the optimal feasibility windows that maximize the utilization on each node, while avoiding overloads. Finally on each node, we use Integer Linear Programming (ILP) to derive fixed priority task attributes that guarantee the task executions within the derived feasibility windows, while keeping the associated costs minimized.

The increasing complexity of real-time systems has lead to the adaptation of component based methods for their development which has a promising potential for faster and more cost effective development of complex real-time systems by facilitating reuse of the real-time components. This is enabled by the components' composition using contracts, which ensures 'correctness by construction'. Modern real-time systems typically consist of mixed criticality components, and scheduling them in a fault-tolerant as well as efficient way, on a distributed platform, is a challenging task. In this paper, we propose a contract-based approach to fault tolerant scheduling of mixed criticality real-time components on a distributed platform, by providing guarantees for the hard real-time components through offline negotiated contracts, as well as flexibility for the soft real-time components through online (re-)negotiated contracts. The proposed approach uses optimization techniques, that uses timing requirements and the recommendations of studies like Fault Hazard Analysis and Zonal Analysis, to provide the contractual parameters for the mixed-criticality components.

Dependability is a vital system requirement, particularly in safety critical and mission critical real-time systems, due to the potentially catastrophic consequences of failures. In most critical applications different fault tolerance mechanisms using redundancy are employed to prevent possible failures. In the case of real-time systems the system designer must ensure that the task set is feasible even under faults, which we refer to as 'fault tolerance feasibility'. Due to cost considerations, often temporal redundancy has been prevalently used to meet this objective.

In this paper we focus on guaranteeing fault-tolerance feasibility under error bursts on uni-processor systems by the usage of resource augmentation, specifically through processor speed-up. Firstly, we derive a processor demand bound based sufficient condition for a set of real-time tasks to be fault tolerance feasible under an assumption that no more than one error burst occurs during the hyper-period of the task set. Subsequently, we derive the necessary resource augmentation bounds (i.e., the processor speed-up), that guarantees the fault tolerance feasibility, if the sufficient test fails. Finally, we prove that, if the error burst length is no more than half the shortest relative deadline of the task set, the minimum processor speed-up required to guarantee fault tolerance feasibility is upper-bounded by 6.