Emerging real-time applications increasingly rely on multicore embedded systems, where tasks must coordinate access to shared local and global resources. Such accesses are protected by critical sections and managed by resource-sharing protocols to ensure mutual exclusion and timing predictability. However, transient faults occurring inside critical sections can corrupt execution and propagate errors across tasks, while directly com- bining conventional locking with fault-tolerance mechanisms can significantly increase blocking. Recent fault-tolerant resource- sharing approaches improve recovery through parallel replica execution, but still suffer from sequential global access and coordination overhead. In previous work, we proposed the Lock- frEe Fault-Tolerant Resource Sharing (LEFT-RS) protocol, which improves fault-tolerant global resource access by allowing con- current critical-section execution. However, LEFT-RS enforces non-preemptive global resource access, which can cause excessive arrival blocking for high-priority tasks and limit schedulability. This paper introduces the CAFT-RS (Ceiling-based Access for Fault-Tolerant Resource Sharing) protocol, which applies a priority-ceiling mechanism to both local and global resource ac- cesses. CAFT-RS allows higher-priority tasks to preempt ongoing global accesses while preserving correctness through dedicated post-preemption rules. We develop a worst-case response-time analysis that accounts for both the reduction in arrival blocking and the additional preemption overhead. Extensive evaluation results show that CAFT-RS improves schedulability by up to 188.5% on average over LEFT-RS.

Emerging real-time applications have driven the transition to multicore embedded systems, where tasks must share resources due to functional demands and limited availability. These resources, whether local or global, are protected within critical sections to prevent race conditions, with locking protocols ensuring both exclusive access and timing requirements. However, transient faults occurring within critical sections can disrupt execution and propagate errors across multiple tasks. Conventional locking protocols fail to address such faults, and integrating traditional fault tolerance techniques often increases blocking. Recent approaches improve fault recovery through parallel replica execution; however, challenges remain due to sequential accessing, coordination overhead, and susceptibility to common-mode faults. In this paper, we propose a Lock-frEe Fault-Tolerant Resource Sharing (LEFT-RS) protocol for multicore real-time systems. LEFT-RS allows tasks to concurrently access and read global resources while entering their critical sections in parallel. Each task can complete its access earlier upon successful execution if other tasks experience faults, thereby improving the efficiency of resource usage. Our design also limits the overhead and enhances fault resilience. We present a comprehensive worst-case response time analysis to ensure timing guarantees. Extensive evaluation results demonstrate that our method significantly outperforms existing approaches, achieving up to an 84.5% improvement in schedulability on average.

Motivated by the performance demands and stringent timing requirements of safety-critical systems like avionics and autonomous vehicles, research has focused on providing timing guarantees for the scheduling of Directed Acyclic Graph (DAG) tasks in multicore systems. The structural complexity and timing anomalies make this problem challenging. Existing methods bound the Worst-Case Response Time (WCRT) of tasks through static analysis, but these bounds are complicated, difficult to validate, and often remain pessimistic for many scheduling scenarios. Runtime intervention can be effective in eliminating timing anomalies and providing timing guarantees; however, it is ineffective for anomaly-free scheduling scenarios, leads to non-work-conserving schedules, and incurs additional overhead. This paper proposes a hybrid approach to identify timing anomalies in DAG scheduling scenarios within a system, providing tighter WCRT solutions. The static analysis first offers a sufficient anomaly test to directly identify some anomaly-free DAG scheduling scenarios. Leveraging a wide range of scheduling data collected from the running system or its simulator, we then apply a machine learning approach to train a binary classification model, achieving an accuracy of 99.5%. Identifying the anomaly status enables the application of more precise WCRT bounds for different scheduling scenarios, leading to improved system performance. Specifically, we shorten the WCRT bounds for anomaly-free DAG scheduling by an average of up to 21.58%, with a maximum reduction of up to 55.47% compared to the state-of-the-art method.

An IDK classifier is a computational element that classifies an input provided to it into one of a set of predefined categories provided that it can achieve the necessary confidence level to do so; otherwise, it outputs “I Don't Know” (IDK). The concept of IDK classifier cascades has emerged as a strategy for striking a balance between the requirements of rapid response and precise classification in machine perception. Effective algorithms for constructing IDK classifier cascades have recently been developed. Here we extend these prior approaches by incorporating fault-tolerance: enabling classification that is concurrently rapid and accurate even in the event of some of the IDK classifiers exhibiting faulty behavior.

In this paper, we use the term “Analysis-Runtime Co-design” to describe the technique of modifying the runtime protocol of a scheduling scheme to closely match the analysis derived for it. Carefully designed modifications to the runtime protocol make the schedulability analysis for the scheme less pessimistic, while the schedulability guarantee afforded to any given application remains intact. Such modifications to the runtime protocol can result in significant benefits with respect to other important metrics. An enhanced runtime protocol is designed for the Adaptive Mixed-Criticality (AMC) scheduling scheme. This protocol retains the same analysis, while ensuring that in the event of high-criticality behavior, the system degrades less often and remains degraded for a shorter time, resulting in far fewer low-criticality jobs that either miss their deadlines or are not executed.

Abstract Timing verification of multi-core systems is complicated by contention for shared hardware resources between co-running tasks on different cores. This paper introduces the Multi-core Resource Stress and Sensitivity (MRSS) task model that characterizes how much stress each task places on resources and how much it is sensitive to such resource stress. This model facilitates a separation of concerns, thus retaining the advantages of the traditional two-step approach to timing verification (i.e. timing analysis followed by schedulability analysis). Response time analysis is derived for the MRSS task model, providing efficient context-dependent and context independent schedulability tests for both fixed priority preemptive and fixed priority non-preemptive scheduling. Dominance relations are derived between the tests, along with complexity results, and proofs of optimal priority assignment policies. The MRSS task model is underpinned by a proof-of-concept industrial case study. The problem of task allocation is considered in the context of the MRSS task model, with Simulated Annealing shown to provide an effective solution.

With ever more complex functionalities being implemented in emerging real-time applications, multi-core systems are demanded for high performance, with directed acyclic graphs (DAG) being used to model functional dependencies. For a single DAG task, our previous work presented a concurrent provider and consumer (CPC) model that captures the node-level dependency and parallelism, which are the two key factors of a DAG. Based on the CPC, scheduling and analysis methods were constructed to reduce makespan and tighten the analytical bound of the task. However, the CPC-based methods cannot support multi-DAGs as the interference between DAGs (i.e., inter-task interference) is not taken into account. To address this limitation, this article proposes a novel multi-DAG scheduling approach which specifies the number of cores a DAG can utilise so that it does not incur the inter-task interference. This is achieved by modelling and understanding the workload distribution of the DAG and the system. By avoiding the inter-task interference, the constructed schedule provides full compatibility for the CPC-based methods to be applied on each DAG and reduces the pessimism of the existing analysis. Experimental results show that the proposed multi-DAG method achieves an improvement up to 80% in schedulability against the original work that it extends, and outperforms the existing multi-DAG methods by up to 60% for tightening the interference.

Timing verification of multi-core systems is complicated by contention for shared hardware resources between co-running tasks on different cores. This paper introduces the Multi-core Resource Stress and Sensitivity (MRSS) task model that characterizes how much stress each task places on resources and how much it is sensitive to such resource stress. This model facilitates a separation of concerns, thus retaining the advantages of the traditional two-step approach to timing verification (i.e. timing analysis followed by schedulability analysis). Response time analysis is derived for the MRSS task model, providing efficient context-dependent and context independent schedulability tests for both fixed priority preemptive and fixed priority non-preemptive scheduling. Dominance relations are derived between the tests, and proofs of optimal priority assignment provided. The MRSS task model is underpinned by a proof-of-concept industrial case study.

Development of dependable multi-/many-core systems requires assurance that the system is operable in a range of conditions, subjected to both functional and non-functional requirements. To achieve this, tools need to be implemented that can enable exploration of design options and be able to detect deficiencies earlier to avoid costly system re-design. In this work we discuss the challenges of design of multi-core realtime systems with timing assurance and discuss what are the requirements for modelling, testing and analysis tools. Digital Twin-based predictive modelling and fast design space evaluation are studied that work toward addressing these challenges.

General-purpose I/O widely exists on multi- and many-core systems. For real-time applications, I/O operations are often required to be timing-predictable, i.e., bounded in the worst case, and timing-accurate, i.e., occur at (or near) an exact desired time instant. Unfortunately, both timing requirements of I/O operations are hard to achieve from the system level, especially for many-core architectures, due to various latency and contention factors presented in the path of instigating an I/O request. This paper considers a dedicated I/O co-processing unit, and proposes two scheduling methods, with the necessary hardware support implemented. It is the first work that guarantees timing predictability and maximises timing accuracy of I/O tasks in the multi-and many-core systems.

With ever more complex functionalities being implemented in emerging real-time applications, multiprocessor systems are demanded for high performance, and directed acyclic graphs (DAGs) are used to model functional dependencies. In this work, we study a single periodic non-preemptive DAG running on a homogeneous multiprocessor platform, which is a common setup in many domains, such as automotive, robotics, and industrial automation. Aiming to reduce the makespan of the DAG and provide a tight yet safe bound, our contributions involve the exploitation of node-level parallelism and inter-node dependency, which are the two key factors of a DAG topology. First, we introduce a concurrent provider and consumer (CPC) model that precisely captures the above two factors, and can be recursively applied when parsing a DAG. Building upon CPC, we propose a novel scheduling method focused on reducing the makespan that orders the nodes in the following sequence: (i) the critical path, (ii) early predecessor paths of the critical path, and (iii) longer paths. Secondly, new response time analysis is presented, which provides a generic bound for any execution order of the non-critical nodes and a specific (tighter) bound for a fixed such order. Comprehensive evaluation demonstrates that our scheduling approach and analysis outperforms the state-of-the-art methods.

This paper introduces the Dirichlet-Rescale (DRS) algorithm. The DRS algorithm provides an efficient general-purpose method of generating n-dimensional vectors of components (e.g. task utilizations), where the components sum to a specified total, each component conforms to individual constraints on the maximum and minimum values that it can take, and the vectors are uniformly distributed over the valid region of the domain of all possible vectors, bounded by the constraints.The DRS algorithm can be used to improve the nuance and quality of empirical studies into the effectiveness of schedulability tests for real-time systems; potentially making them more realistic, and leading to new conclusions. It is efficient enough for use in large-scale studies where millions of task sets need to be generated. Further, the constraints on individual task utilizations can be used for fine-grained control of task set parameters enabling more detailed exploration of schedulability test behavior. Finally, the real power of the algorithm lies in the fact that it can be applied recursively, with one vector acting as a set of constraints for the next. This is particularly useful in task set generation for mixed criticality systems and multi-core systems, where task utilizations are either multi-valued or can be decomposed into multiple constituent parts.

This article describes the motivation, design, analysis, and configuration of the criticality-aware multi-hop wireless communication protocol AirTight. Wireless communication has become a crucial part of the infrastructure of many cyber-physical applications. Many of these applications are real-time and also mixed-criticality, in that they have components/subsystems with different consequences of failure. Wireless communication is inevitably subject to levels of external interference. In this article, we represent this interference using a criticality-aware fault model; for each level of temporal interference in the fault model, we guarantee the timing behaviour of the protocol (i.e., we guarantee that packet deadlines are satisfied for certain levels of criticality). Although a new protocol, AirTight is built upon existing standards such as IEEE 802.15.4. A prototype implementation and protocol-accurate simulator have been produced. This article develops a series of schedulability analysis techniques for single-channel and multichannel wireless Cyber-Physical Systems (CPS). Heuristics are specified and evaluated as the starting point of design space exploration. Genetic algorithms are then defined and evaluated to assess their performance in developing schedule tables incorporating multichannel allocations in these systems.

The ever-growing complexity of safety-critical control systems continues to require evolution in control system design, architecture and implementation. At the same time the cost of developing such systems must be controlled and importantly quality must be maintained. This paper examines the application of Mixed Criticality System (MCS) research to a DAL-A aircraft engine Full Authority Digital Engine Control (FADEC) system which includes studying porting the control system’s software to a preemptive scheduler from a non-preemptive scheduler. The paper deals with three key challenges as part of the technology transitions. Firstly, how to provide an equivalent level of fault isolation to ARINC 653 without the restriction of strict temporal slicing between criticality levels. Secondly extending the current analysis for Adaptive Mixed Criticality (AMC) scheduling to include the overheads of the system. Finally the development of clustering algorithms that automatically group tasks into larger super-tasks to both reduce overheads whilst ensuring the timing requirements, including the important task transaction requirements, are met.

This paper describes four impact case studies where real-time systems research has been successfully transferred into industrial practice. In three cases, the technology created was translated into a viable commercial product via a start-up company. This technology transfer led to the creation and sustaining of a large number of high technology jobs over a 20 year period. The final case study involved the direct transfer of research results into an engineering company. Taken together, all four case studies have led to significant advances in automotive electronics and avionics, providing substantial returns on investment for the companies using the technology.

This paper describes the motivation, design, analysis and implementation of a new protocol for critical wireless communication called AirTight. Wireless communication has become a crucial part of the infrastructure of many cyber-physical applications. Many of these applications are real-time and also mixed-criticality, in that they have components/subsystems with different consequences of failure. Wireless communication is inevitably subject to levels of external interference. In this paper we represent this interference using a criticality-aware fault model; for each level of interference in the fault model we guarantee the timing behaviour of the protocol (i.e. we guarantee that packet deadlines are satisfied for certainly levels of criticality). Although a new protocol, AirTight is built upon existing standards such as IEEE 802.15.4. A prototype implementation and protocol-accurate simulator, which are also built upon existing technologies, demonstrate the effectiveness and functionality of the protocol.

Certification authorities require correctness and survivability. In the temporal domain this requires a convincing argument that all deadlines will be met under error free conditions, and that when certain defined errors occur the behaviour of the system is still predictable and safe. This means that occasional execution-time overruns should be tolerated and where more severe errors occur levels of graceful degradation should be supported. With mixed-criticality systems, fault tolerance must be criticality aware, i.e. some tasks should degrade less than others. In this paper a quantitative notion of robustness is defined, and it is shown how fixed priority-based task scheduling can be structured to maximise the likelihood of a system remaining fail operational or fail robust (the latter implying that an occasional job may be skipped if all other deadlines are met). Analysis is developed for fail operational and fail robust behaviour, optimal priority ordering is addressed and an experimental evaluation is described. Overall, the approach presented allows robustness to be balanced against schedulability. A designer would thus be able to explore the design space so defined.

Supporting sustainable development for the urban environment is crucial in the age of rapid urbanisation. Air pollution modelling is one of the key tools for researchers, scientists, and urban planners to understand pollution behaviour. Recent updates in air quality regulations are challenging the state-of-the-art air pollution modelling techniques by requiring accurate predictions on a high temporal level, i.e. predictions at the hourly level rather than the annual level. Current state-of-the-art models designed to have good prediction accuracy on the low temporal resolution by assuming that the pollution is in steady state. Making predictions on higher temporal resolution violates this assumption and causing inaccurate predictions. We introduce a novel statistical regression based air pollution model which produces accurate hourly predictions by using data with high temporal resolution and advanced regression algorithms. We conducted an analysis which shows that the state-of-the-art evaluation techniques (e.g. RMSE) do not describe the nature of the mispredictions of the models built on different data subsets. We carried out an extensive input data evaluation experiment where we concluded that our approach could achieve further accuracy improvement by training the models on a carefully selected subset of the input data.

Intrinsic timing uncertainties present in modern hardware platforms have motivated the use of Extreme Value Theory (EVT) to timing analysis, however, the timing behaviour of a task may not entirely fulfil the necessary assumptions. To deal with this difficulty, randomisation at the hardware level has been proposed as a means of facilitating the use of statistical timing analysis. However, it has been shown that hardware randomisation does not solve all the analysis problems and importantly some projects may not wish to change the hardware that is used to support timing analysis. This paper presents an innovative approach, which does not require hardware randomisation or any special system feature, named Indirect Estimation in Statistical Time Analysis (IESTA). The main difference is that randomised hardware is performed before software instructions actually executes and is applied to parameters (e.g. cache state) only indirectly linked to timing. In contrast, IESTA adds its randomisation directly to the timing measures without affecting the way the software is executed. The IESTA approach is evaluated by experiments on two real case studies for which execution time measurements are taken from an embedded platform and from a Rolls-Royce Full Authority Digital Engine Controller.

To move mixed criticality research into industrial practice requires models whose run-time behaviour is acceptable to systems engineers. Certain aspects of current models, such as abandoning lower criticality tasks when certain situations arise, do not give the robustness required in application domains such as the automotive and aerospace industries. In this paper a new bailout protocol is developed that still guarantees high criticality software but minimises the negative impact on lower criticality software via a timely return to normal operation. We show how the bailout protocol can be integrated with existing techniques, utilising both offline slack and online gain-time to further improve performance. Static analysis is provided for schedulability guarantees, while scenario-based evaluation via simulation is used to explore the effectiveness of the protocol.

Body Sensor Networks (BSNs) are being used across a wider range of applications including healthcare ones where sensors may be attached to the body to sense certain properties including Electrocardiogram (ECG). The dependability of the systems is a key concern and is affected by the way in which it is used. For example, if the leads are loosely attached then the resulting signal will not be useful. It has been reported that the rate of such error is around 4% in the intensive care unit [8] when operating medical devices by trained professionals. The problem is made worse as the users of the systems are often not trained professionals. Some work has been performed on detecting anomalous signals. However, all of it has concentrated on anomalies caused by medical conditions (e.g arrhythmia). That is, to the best of our knowledge, no prior work has looked at anomalies caused by incorrect usage. In this paper a range of usage anomalies are defined in conjunction with a cardiologist and a lightweight algorithm is developed that achieves a high identification rate.

The use of increasingly complex hardware and software platforms in response to the ever rising performance demands of modern real-time systems complicates the verification and validation of their timing behaviour, which form a time-and-effort-intensive step of system qualification or certification. In this paper we relate the current state of practice in measurement-based timing analysis, the predominant choice for industrial developers, to the proceedings of the PROXIMA (Probabilistic real-time control of mixed-criticality multicore systems) project in that very field. We recall the difficulties that the shift towards more complex computing platforms causes in that regard. Then we discuss the probabilistic approach proposed by PROXIMA to overcome some of those limitations. We present the main principles behind the PROXIMA approach as well as the changes it requires at hardware or software level underneath the application. We also present the current status of the project against its overall goals, and highlight some of the principal confidence-building results achieved so far.

Establishing Worst Case Execution Times (WCET) using Measurement-Based Timing Analysis (MBTA) is only effective if we have reasonable confidence that we have fed the worst case execution trace into the analysis. Therefore for certification, the quality of these traces is of paramount importance. This paper aims to investigate how search algorithms can be used to automatically, and reliably, generate test cases so that appropriate execution traces are available to support MBTA. The work carried out in this paper uses a standard search algorithm and created a number of fitness functions to target the generation of 'good data'. The results are then input into a commercial measurement-based WCET analysis tool. The new fitness functions focus on achieving a combination of full branch coverage and a high number of loop counts, or partial path coverage, however are shown to achieve reliable approximations of the WCET particularly when combined with an MBTA tool. The code items used for the analysis included off the shelf benchmarks, as well as industrial safety-critical aircraft engine control software.

Communication between nodes in Wireless Sensor Networks (WSNs) can be interrupted by body movement. With the demand of the use of WSNs in health monitoring systems, it is necessary to investigate and provide a solution to overcome the interference caused by human body parts. The body parts such as the elbow and knee can reflect, absorb or obstruct the radio signal that can disrupt the radio communication. This can increase the energy consumption due to retransmission. In this paper, we have proposed the Enhanced Opportunistic Transmission Protocol that utilizes the kinematic reading to improve the transmission reliability. Our experimental result obtained from sixty participants has shown that the E-OTP can delivery the packet with a higher Packet Delivery Ratio using smaller number of transmissions compared to two other protocols. Our experiments have also shown that the successful transmission can be achieved as long as the node transmits its packet when leg is above the midpoint forward position.

To move mixed criticality research into industrial practice requires models whose run-time behaviour is acceptable to systems engineers. Certain aspects of current models, such as abandoning lower criticality tasks when certain situations arise, do not give the robustness required in application domains such as the automotive and aerospace industries. In this paper a new bailout protocol is developed that still guarantees high criticality tasks but minimises the negative impact on lower criticality tasks via a timely return to normal operation. We show how the bailout protocol can be integrated with existing techniques, utilising offline slack to further improve performance. Static analysis is provided for the strong schedulability guarantees, while scenario based evaluation via simulation is used to explore the effectiveness of the protocol.

Safety cases need significant amount of time and effort to produce. The required amount of time and effort can be dramatically increased due to system changes as safety cases should be maintained before they can be submitted for certification or re-certification. Sensitivity analysis is useful to measure the flexibility of the different system properties to changes. Furthermore, contracts have been proposed as a means for facilitating the change management process due to their ability to record the dependencies among system's components. In this paper, we extend a technique that uses a sensitivity analysis to derive safety contracts from Fault Tree Analyses (FTA) and uses these contracts to trace changes in the safety argument. The extension aims to enabling the derivation of hierarchical and correlated safety contracts. We motivate the extension through an illustrative example within which we identify limitations of the technique and discuss potential solutions to these limitations.

Software engineering researchers have extensively explored the reuse of components at source-code level. Contracts explicitly describe component behaviour, reducing development risk by exposing potential incompatibilities early in the development process. But to benefit fully from reuse, developers of safety-critical systems must also reuse safety evidence. Full reuse would require both extending the existing notion of component contracts to cover safety properties and using these contracts in both component selection and system certification. This is not as simple as it first appears. Much of the review, analysis, and test evidence developers provide during certification is system-specific. This makes it difficult to define safety contracts that facilitate both selecting components to reuse and certifying systems. In this paper, we explore the definition and use of safety contracts, identify challenges to component-based software reuse safety-critical systems, present examples to illustrate several key difficulties, and discuss potential solutions to these problems.

Timing is often seen as the most important property of systems after function, and safety-critical systems are no exception. In this paper, we consider how timing is typically treated in safety assurance and, in particular, the safety arguments being proposed by industry and academia. A critique of these arguments is performed based on how systems are generally developed and how evidence is gathered. Significant weaknesses are exposed resulting in a more appropriate safety argument being proposed. As part of this work techniques for identifying relationships, in the form of contracts, between parts of the argument and the strength of evidence are used. The work is demonstrated using a Computer-Assisted Braking example, specifically an Anti-Lock Braking System for a car, as it is a classic example of a component that may be used ‘Out of Context’, as discussed in a number of safety standards, and may also be reused across a number of systems as well as part of a product line.

Currently the main approach used to save power within WSN's is to employ reactive MAC schemes that detect when the network is becoming busy and adapt to provide an increase in available bandwidth. Once the traffic becomes lighter the available bandwidth is reduced to save power. While this works well with bursty sporadic traffic, there is a clear trade-off between latency of response and power savings. Other problems with this approach include hard to derive parameters along with their poor performance in periodic sense-and-send applications due to their reactive nature. We propose an adaptive feedback-based scheme that adjusts the duty cycle of the the motes to reduce the power consumed in typical sense-and-send applications by 58.4%, while still meeting a minimal level of service specified by the operator. Such an adaptive scheme is necessary to minimise power consumption as the complete network characteristics are unknown prior to deployment, and can change during runtime. Our approach is independent of node distribution and is also MAC layer agnostic, unlike the current state-of-the-art, whilst consuming less power. Our approach provides a simple method for the application designer to modify its behaviour, whilst allowing WSNs to operate longer and provide the same level of service as current approaches.

Wireless Sensor Networks (WSNs) are being developed and deployed in a wide range of Cyber-Physical systems, some of which must be dependable, e.g. in assisted living facilities where their failure could lead to an accident. In this paper, it is shown that the state of the art approaches do not meet the needs of dependability that these applications require. The main reason is an issue is the unpredictable physical environment in which they operate. Currently there is little emphasis on how these systems behave when failures occur, instead authors emphasise average case performance. Consequently there is little understanding of how and why systems fail and the possible consequences e.g. a system hazard. In this paper simulated tests are used at run-time to check key dependability properties of the system. The results of these tests are used to plan maintenance, thus ensuring available and reliable operation, and determining when the system is at risk of subjecting people to unacceptable hazards such that appropriate steps can be taken. Our approach has been show to perform with 15% less time at risk than the current state-of-the art.

Wireless Sensor Networks (WSN) are now being used in a range of applications, many of which are critical systems, e.g. monitoring assisted living facilities or for fire detection systems which is the example used in this paper. For critical systems it is important to be able to determine the minimum number of failures that can cause a hazard to occur. This is normally a manual, human intensive, task. This paper presents a novel application of search to both the WSN and safety domains; searching for combinations of failures that can cause a hazard and then reducing these to the minimum possible using a combination of automated search and manual refinement. Due to the size and complexity of the search problem, a parallel search algorithm is designed that runs on available compute resources with the results being processed using R.

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.

Increased levels of automation together with increased complexity of automation systems brings increased responsibility on the system developers in terms of quality demands from the legal perspectives as well as company reputation. Component based development of software systems provides a viable and cost-effective alternative in this context provided one can address the quality and safety certification demands in an efficient manner. In this paper we present our vision, challenges and a brief outline of various research themes in which our team is engaged currently within two major projects.

Testing a new network protocol experimentally in WSNs is an important step prior to deployment because theoretical models and assumptions made often differ between real environmental properties and performance. It is imperative to ensure that the results obtained from the test are reliable and the performance observed in simulation is a valid representation of the real world. Thus there is a need to perform extensive experimental analysis and evaluation to produce results with an acceptable level of confidence. In this paper, we outline experimental statistical and analysis techniques that allow us to have some confidence in the results obtained are at least relevant to physical deployment. Using the results from hardware and software experiments, we apply our proposed Experimental Verification Process (EVP) to evaluate the performance of the Multimodal Routing Protocol (MRP) against Adhoc On-demand Distance Vector (AODV) and Not So Tiny-AODV (NST-AODV). With the EVP, we have improved the credibility of MRP.

Real-time embedded systems are becoming ever more complex. We are reaching the stage where even if static Response-Time Analysis (RTA) was feasible from a cost and technical perspective, the results of such an analysis are overly pessimistic. This makes them less useful to the practitioner. In addition, the temporal validation and verification of such systems in some applications, e.g., aeronautics, requires the probability of obtaining a worst-case response time larger than a given value in order to support dependable system functions. All these facts advocate moving toward statistical RTA, which instead of calculating absolute worst-case timing guarantees, computes a probabilistic worst-case response time estimate. The contribution of this paper is to present and evaluate such a statistical RTA technique which uses a black box view of the systems under analysis, by not requiring estimates of parameters such as worst-case execution times of tasks. Furthermore, our analysis is applicable to real systems that are complex, e.g., from a task dependencies perspective.

Interactions between multiple tunable protocol parameters and multiple performance metrics are generally complex and unknown; finding optimal solutions is generally difficult. However, protocol tuning can yield significant gains in energy efficiency and resource requirements, which is of particular importance for sensornet systems in which resource availability is severely restricted. We address this multi-objective optimization problem for two dissimilar routing protocols and by two distinct approaches. First, we apply factorial design and statistical model fitting methods to reject insignificant factors and locate regions of the problem space containing near-optimal solutions by principled search. Second, we apply the Strength Pareto Evolutionary Algorithm 2 and Two-Archive evolutionary algorithms to explore the problem space, with each iteration potentially yielding solutions of higher quality and diversity than the preceding iteration. Whereas a principled search methodology yields a generally applicable survey of the problem space and enables performance prediction, the evolutionary approach yields viable solutions of higher quality and at lower experimental cost. This is the first study in which sensornet protocol optimization has been explicitly formulated as a multi-objective problem and solved with state-of-the-art multi-objective evolutionary algorithms.

This paper describes the tool support for a framework for performing statistical WCET analysis of realtime embedded systems by using bootstrapping sampling and Extreme Value Theory (EVT). To be specific, bootstrapping sampling is used to generate timing traces, which not only fulfill the requirements given by statistics and probability theory, but also are robust to use in the context of estimating the WCET of programs. Next, our proposed statistical inference uses EVT to analyze such timing traces, and computes a WCET estimate of the target program, pertaining to a given predictable probability. The evaluation results show that our proposed method could have the potential of being able to provide a tighter upper bound on the WCET estimate of the programs under analysis, when compared to the estimates given by the referenced WCET analysis methods.

Sensornets are often deployed into inaccessible, dangerous, or changeable physical environments. Centralised control and management is generally infeasible. Autonomous, self-configuring, and self-managing mechanisms are required to provide a suitable infrastructure which reliably supports distributed applications, hiding any underlying instability. The Lightweight Integrated Protocol Suite (LIPS) coordinates time-sensitive activity, and regulates network size and density, in self-managing cellular sensornets. Although components can be implemented in isolation, each contributes part of a larger, integrated solution.

Field Programmable Gate Arrays (FPGAs) are highly configurable programmable logic devices. They offer many benefits over traditional micro-processors such as the ability to efficiently run tasks in parallel and also highly predictable timing performance. They are becoming increasingly popular for use in the safety critical domain where predictability is essential. However, concerns about their dependability, principally their reliability and difficulties in assessing the impact of an internal failure means that current designs are inefficient and conservative. This paper discusses these issues in depth. It also presents an FPGA task allocation method using simulated annealing to balance efficiency and reliability requirements. This can be used to improve designs of safety critical FPGA based systems.

In a number of areas, for example, sensor networks and systems of systems, complex networks are being used as part of applications that have to be dependable and safe. A common feature of these networks is they operate in a de-centralised manner and are formed in an ad-hoc manner and are often based on individual nodes that were not originally developed specifically for the situation that they are to be used. In addition, the nodes and their environment will have different behaviours over time, and there will be little knowledge during development of how they will interact. A key challenge is therefore how to understand what behaviour is normal from that which is abnormal so that the abnormal behaviour can be detected, and be prevented from affecting other parts of the system where appropriate recovery can then be performed. In this paper we review the state of the art in bio-inspired approaches, discuss how they can be used for error detection as part of providing a safe dependable sensor network, and then provide and evaluate an efficient and effective approach to error detection.

Current approaches to instruction cache analysis for determining worst-case execution time rely on building a mathematical model of the cache that tracks its contents at all points in the program. This requires perfect knowledge of the functional behaviour of the cache and may result in extreme complexity and pessimism if many alternative paths through code sections are possible. To overcome these issues, this paper proposes a new hybrid approach in which information obtained from program traces is used to automate the construction of a model of how the cache is used. The resulting model involves the learning of a Bayesian network that predicts which instructions result in cache misses as a function of previously taken paths. The model can then be utilised to predict cache misses for previously unseen inputs and paths. The accuracy of this learned model is assessed against real benchmarks and an established statistical approach to illustrate its benefits.

It is with great pleasure that we accepted the privilege of editing this special issue of Software: Practice and Experience on the practical aspects of Search-based Software Engineering.Software systems are becoming ever larger and more complex as new architectures emerge, high-performance hardware becomes increasingly affordable, and systems must satisfy often highly constrained operating requirements.However, many traditional approaches to software design and implementation are unable to scale to meet the challenges presented by such systems.For this reason, a recent trend has been to automate tasks within the software engineering life cycle using machine-based search; this approach is known as Search-based Software Engineering (SBSE).The engineering task is reformulated as an optimization problem and solutions are found using efficient modern optimization algorithms, such as meta-heuristic search and operational research methods.SBSE promises much greater scalability than traditional labour-intensive methods since human effort is redirected to guide the search for solutions to the engineering problem, rather than perform the search itself.SBSE has been applied across the spectrum of software engineering activities, including: requirements engineering, project planning, software task allocation, code refactoring, protocol synthesis, test data generation, and the design of algorithms for highly resource-constrained hardware platforms.As the efficacy and scalability of this approach is established for an increasing number of software engineering problems, an emerging research interest is how to successfully use SBSE in practice.It was this focus on the practical experience of applying SBSE that defined this special issue.Following the initial call for papers, we received 18 manuscripts of which 5 were eventually accepted for this special issue, and a further paper being accepted for a regular issue of the journal.The accepted papers provide an interesting balance between solving practical problems within software engineering-which would be very costly to solve, if it is possible at all, using traditional methods-and demonstrating how existing solutions can be applied to real problems.The first paper, 'Evolutionary Deployment Optimization for Service Oriented Clouds', deals with a classic multi-objective problem that is a variant of the task allocation problem.In this paper the problem of allocating services to the available resources is considered such that the performance, and hence Service Level Agreements (SLA), for the cloud-based system are met.To achieve this requires carefully balanced trade-offs to be made based on statistical analysis of how the system will perform.For this purpose a genetic algorithm is deployed which manages to solve the problems resulting in a number of Pareto-optimal solutions.The work is demonstrated through a mix of empirical methods and a case study applied to a loan validator system.The second paper, 'The use of Search-based Optimization Techniques to Schedule and Staff Software Projects: An Approach and an Empirical Study', considers a related problem of how to allocate jobs to staff working on a software engineering project.Both single objective and multi-objective formulations of the problem are considered, the latter attempting to minimize, for example, both completion time and schedule fragmentation.A variety of search algorithms are applied to solve both formulations and their efficacy evaluated.The solution to the multi-objective formulation is a set of schedules illustrating different trade-offs between the competing objectives from which a project manager can choose.The work is demonstrated on two large-scale commercial software projects.The third paper, 'Automated Scheduling for Clone-based Refactoring using a Competent GA', addresses the highly important issue of the order in which to refactor software.Refactoring is another term for modifying software and it is widely recognized that the order has direct

This paper presents a novel approach to timing analysis of complex real-time systems containing data-driven tasks with intricate execution dependencies. Using a system model inspired by industrial control systems, we show how the execution time of tasks can be represented as a mathematical expression instead of a single numeric value. Next, based on this more detailed modeling, we introduce a concrete process of formally obtaining the exact value of both Worst-Case Execution-Time (WCET) and Worst-Case Response-Time (WCRT) of tasks by using upper-part binary search and TIMES (a timed model checker). Finally, in order to show the potential of the proposed approach, we apply it to a model created from a real robotic control system for which the traditional way of obtaining a WCET estimate (through static WCET analysis) on tasks for usage in basic RTA is not appropriate. Our results indicate a significant reduction of pessimism when compared to basic RTA using WCET estimates on tasks given by a basic assumption.

Storing instructions in caches has led to dramatic increases in the speed at which programs can execute. However, this has also made it harder to reason about the time needed for execution in those domains where temporal behaviour of code is important. This paper presents a novel approach to predicting which instructions will be found in the cache when required using machine learning. More specifically, we demonstrate a method in which a Bayesian network is inferred from examples of a program running and is then used to predict the presence of instructions in the cache when the same program is run with unknown inputs.

Sensornets provide coverage of physical phenomena over extended periods, perhaps months or years. However, active nodes may deplete finite batteries within days, and are prone to failure. The sensornet application may require a given number of active nodes within each region to provide appropriate sensor redundancy and processing capacity. If many nodes are deployed, at any given time a smaller working set of the correct size can be selected for duty. In this paper we present a lightweight approach to active population management. An omniscient overview of network state is not required, and expensive communication activity is minimised. Probabilistic methods are employed, ensuring that individual nodes can make appropriate decisions using only locally available information.

As modern processors can execute instructions at far greater rates than these instructions can be retrieved from main memory, computer systems commonly include caches that speed up access times. While these improve average execution times, they introduce additional complexity in determining the Worst Case Execution Times crucial for Real-Time Systems. In this paper, an approach is presented that utilises Bayesian Networks in order to more accurately estimate the worst-case caching behaviour of programs. With this method, a Bayesian Network is learned from traces of program execution that allows both constructive and destructive dependencies between instructions to be determined and a joint distribution over the number of cache hits to be found. Attention is given to the question of how the accuracy of the network depends on both the number of observations used for learning and the cardinality of the set of potential parents considered by the learning algorithm.

Interaction between sensornet nodes and the physical environment in which they are embedded implies realtime requirements. Application tasks must be executed in the correct place, and in the correct order, for correct application behaviour. Sensornets generally have no global clock, and incur unacceptable cost if traditional synchronisation protocols are implemented. We present a lightweight primitive which generates a periodic sequence of synchronisation events which are coordinated across large sensornets structured into clusters or cells. Two biologically-inspired mechanisms are combined; desynchronisation within cells, and synchronisation between cells. This hierarchical coordination provides a global basis for local application-driven timing decisions at each node.

Sensornet designers seek to maximize energy efficiency while maintaining acceptable Quality of Service. However, the interactions between multiple tunable protocol parameters and multiple performance metrics are generally complex and unknown, and combinatorial explosion renders impossible any exhaustive search approach. Most work published to date employs seemingly arbitrary choices of protocol parameters, derived by informal judgement and limited trial and error experiments. This lack of rigour may lead to sub-optimal parameter selection and sub-optimal network behaviour, and may mask the real performance differences of dissimilar protocols. We describe a reusable engineering method to address this multi-dimensional optimization problem, based on sound engineering principles widely recognized and applied beyond Computer Science. We provide a mechanism with which to de-risk deployment of sensornets tuned within training environments, and evaluate the robustness of these tunings to changing environments. The mechanism is also useful for comparative evaluation of protocols within a fixed deployment context.

Determination of accurate estimates for the Worst-Case Execution Time of a program is essential for guaranteeing the correct temporal behavior of any Real-Time System. Of particular importance is tightly bounding the number of iterations of loops in the program or excessive undue pessimism can result. This paper presents a novel approach to determining the number of iterations of a loop for such analysis. Program traces are collected and analyzed allowing the number of loop executions to be parametrically determined safely and precisely under certain conditions. The approach is mathematically proved to be safe and its practicality is demonstrated on a series of benchmarks.

Component-based and modular software development techniques have become established in recent years. Without complementary verification and certification methods the benefits of these development techniques are reduced. As part of certification, it is necessary to show a system is acceptably safe which subsumes both the normal and abnormal (failure) cases. However, nonfunctional properties, such as safety and failures, are abstraction breakers, cutting across multiple components. Also, much of the work on component-based engineering has been applied to software-based systems rather than field programmable gate array (FPGA)-based systems whose use is becoming more popular in industry. In this paper, we show how a modular design embedded on a FPGA can be exhaustively analyzed (from a safety perspective) to derive the failure and safety properties to give the evidence needed for a safety case. The specific challenges faced are analyzing the fault characteristics of individual electronic components, combining the results across software modules, and then feeding this into a system safety case. A secondary benefit of taking this approach is that there is less uncertainty in the performance of the device, hence, it can be used for higher integrity systems. Finally, design improvements can be specifically targeted at areas of safety concern, leading to more optimal utilization of the FPGA device.

One of the most important properties of a good software engineering process and of the design of the software it produces is robustness to changing requirements. Scenario-based analysis is a popular method for improving the flexibility of software architectures. This paper demonstrates a search-based technique for automating scenario-based analysis in the software architecture deployment view. Specifically, a novel parallel simulated annealing search algorithm is applied to the real-time task allocation problem to find baseline solutions which require a minimal number of changes in order to meet the requirements of potential upgrade scenarios. Another simulated annealing-based search is used for finding a solution that is similar to an existing baseline when new requirements arise. Solutions generated using a variety of scenarios are judged by how well they respond to different system requirements changes. The evaluation is performed on a set of problems with a controlled set of different characteristics.

Previous research in supervised and unsupervised anomaly detection normally employ a static model of normal behaviour (normal-model) throughout the lifetime of the system. However, there are real world applications such as swarm robotics and wireless sensor networks where what is perceived as normal behaviour changes accordingly to the changes in the environment. To cater for such systems, dynamically updating the normal-model is required. In this paper, we examine the requirements from a range of distributed autonomous systems and then propose a novel unsupervised anomaly detection architecture capable of online adaptation inspired by the vertebrate immune system.

The lifespan, and hence utility, of sensornets is limited by the energy resources of individual motes. Network designers seek to maximise energy efficiency while maintaining an acceptable network quality of service. However, the interactions between multiple tunable protocol parameters and multiple sensornet performance metrics are generally complex and unknown. In this paper we address this multi-dimensional optimisation problem by two distinct approaches. Firstly, we apply a Design Of Experiments approach to obtain a generalised linear interaction model, and from this derive an estimated near-optimal solution. Secondly, we apply the Two-Archive evolutionary algorithm to improve solution quality for a specific problem instance. We demonstrate that, whereas the first approach yields a more generally applicable solution, the second approach yields a broader range of viable solutions at potentially lower experimental cost.

Wireless sensor networks require shared medium access management to prevent collisions, message corruption and other unhelpful effects. Cellular sensornets require minimal energy consumption to maximise network lifetime, and management of interaction with base stations and other cells. We present a protocol which dynamically generates a near-optimal duty schedule within a cell such that communication duty is shared evenly between participating nodes with exactly one node on-duty at any given time.

Sensornets must allocate limited computation and energy resources efficiently to maximise utility and lifetime. This task is complicated by the need to coordinate activity between nodes as sensornets are necessarily real-time collaborative systems. In this paper we present and evaluate lightweight adaptive protocols based on pulse-coupled oscillators to synchronise tasks within a unicellular sensornet. A near-optimal schedule is constructed and dynamically maintained under non-ideal network conditions.

Static analysis can be used to determine safe estimates of Worst Case Execution Time. However, overestimation of the number of loop iterations, particularly in nested loops, can result in substantial pessimism in the overall estimate. This paper presents a method of determining exact parametric values of the number of loop iterations for a particular class of arbitrarily deeply nested loops. It is proven that values are guaranteed to be correct using information obtainable from a finite and quantifiable number of program traces. Using the results of this proof, a tool is constructed and its scalability assessed.

Most software engineering methods require some form of model populated with appropriate information. Real-time systems are no exception. A significant issue is that the information needed is not always freely available and derived it using manual methods is costly in terms of time and money. Previous work showed how machine learning information derived during software testing can be used to derive loop bounds as part of the Worst-Case Execution Time analysis problem. In this paper we build on this work by investigating the issue of branch prediction.

There is a vast amount of existing work that investigates energy aware computing. However to exploit the best possible solution requires a system wide approach to design. To design and optimise a whole system at once is not scalable. A viable alternative is component-based engineering approaches where individual parts of the system are designed whilst allowing for the interactions with the rest of the system. The contributions of this paper are a method by which flexibility in the design of applications can be exploited to give the most energy efficient requirements in a computationally efficient way and an exploration of how different computational models relate to the most energy efficient requirements. The results show that the most obvious choice of requirements is not always the best and the overheads due to specific computational models are significant. While carrying out this work, power / energy anomalies, similar in nature to the timing anomalies already identified for worst-case execution time and multiprocessor systems, have been uncovered.

Previous research which has considered task allocation and fault-tolerance together has concentrated on constructing schedules which accommodate a fixed number of redundant tasks. Often, all faults are treated as being equally severe. There is little work which combines task allocation with architectural level fault-tolerance issues such as the number of replicas to use and how they should be configured, both of which are tackled by this work. An accepted method for assessing the impact of a combination of faults is to build a system utility model which can be used to assess how the system degrades when components fail. The key challenge addressed here is how to design objective functions based on a utility model which can be incorporated into a search algorithm in order to optimise fault-tolerance properties. Other issues such as how to extend the local search neighbourhood and balance objectives with schedulability constraints are also discussed.

Real-time systems are becoming more complex at the same time as the expectation of adaptability and dependability rises. Traditional methods for ensuring no faults in the design or identifying their source are labour intensive and overly restrictive. In this paper we explore how concepts of AIS can be applied to RTS to aid their design and maintenance. Contributions are made to both the AIS and RTS communities.

Handling mode changes is one of the most complex and important problems for real-time systems designers. The challenge is to move a system from running one set of software to another while still achieving the quality of service guarantees necessary. There has been previous work which concentrated on how to perform scheduling and timing analysis of mode changes. However, a common theme of all this research is that if the system's schedule and allocation is chosen to minimise the set of differences between modes then the mode transition problem can be performed more easily and quickly. This paper investigates how this can be achieved

Most development, verification and validation methods in software engineering require some form of model populated with appropriate information. Realtime systems are no exception. However a significant issue is that the information needed is not always available. Often this information is derived using manual methods, which is costly in terms of time and money. In this paper we show how techniques taken from other areas may provide more effective and efficient solutions. More specifically machine learning is applied to the problem of automatically deriving loop bounds. The paper shows how taking an approach based on machine learning allows a difficult problem to be addressed with relative ease.

The development of many systems suffer from unexpected problems during development leading to time and cost penalties. A common situation that leads to problems is when components are integrated and un-anticipated features are formed. These features are often termed emergent properties. In this paper, a compositional approach is adopted where components are parameterized with extra information that can then be used to understand the implications of integration and mapping.

Advanced micro-architectural features such as caches and branch prediction mechanisms supporting speculative execution are becoming commonplace within modern microprocessors. For developers of real-time systems, these mechanisms present predictability problems. Previous work has demonstrated accurate analysis for instruction caches, data caches, and branch prediction mechanisms are possible. However, the integration of these individual analysis methods is difficult to do without large increases in computational complexity or the introduction of pessimism regarding the worst-case execution time (WCET) estimate. In this paper, we discuss how a previously published analysis method for branch predictors can be integrated with instruction pipeline analysis.

Advances in scheduling theory have given designers of control systems greater flexibility over their choice of timing requirements. Advances in scheduling theory have given designers of control systems greater flexibility over their choice of timing requirements. This could lead to systems becoming more responsive, more flexible and more maintainable. However, experience has shown that engineers find it difficult to exploit these advantages due o the difficulty in determining the "real" timing requirements of systems and therefore the techniques have delivered less benefit than expected. Part of the reason for this is that the models used by engineers when developing systems do not allow for emergent properties such as timing. This paper presents an approach and framework for addressing the problem of identifying an appropriate and valid set of timing requirements and their corresponding control parameters based on a combination of static analysis and simulation.

This paper investigates the implications of using modern superscalar processors in the safety-critical domain. Firstly, a description of current certification practice and devices is given as background. This is followed by an exposition of the certification argument for a processor when used in a safety-critical application. Throughout the presentation of the argument two types of modern processor are considered, commercial off-the-shelf (COTS) processors and purpose-designed bespoke devices. This allows the elaboration of positive and negative features of processors that can be used as part of the selection (for COTS) or design (for bespoke) process.

The purpose of this paper is to investigate the issues related to task attribute assignment on an individual processor. The majority of papers on fixed priority scheduling make the assumption that tasks have their attributes (deadline, period, offset and priority) pre-assigned. This makes priority assignment trivial. However in practice, the system's timing requirements are specified and it is expected that the task attributes are synthesised from these. This paper is to present work that has been developed to solve this problem.

The paper describes work carried out to reduce the pessimism in distributed systems timing analysis. The starting point for the paper is the need to prove that the timing properties of a system are met in an efficient and effective manner. The paper shows that an exact approach to the analysis can be intractable, and other approaches are too pessimistic. Using extensive simulation, based on realistic requirements from the domain of interest, a new approach to distributed timing analysis is developed using an integrated approach to task attribute assignment and timing analysis. The new approach is up to 20% more effective than previous tractable approaches. An additional benefit is the approach has a greater resilience to change than the other approaches considered. The results contained within the paper demonstrate the effectiveness of our approach.