Trace clustering techniques are often used to assist in discovering different process scenarios. Most existing trace clustering methods aim to partition the event log into different subsets of logs where event traces in the same subset most likely belong to the same scenario. Typically, the partitioning is based on certain patterns, the similarity between the traces, or done by discovering a process model for each cluster of traces. However, most algorithms achieve this by solely using an event log, without allowing the domain expert to influence the discovery in any way. The domain expert may have certain domain expertise which should be exploited to create better process scenario models. This paper presents a density-based trace clustering technique based on expert knowledge to assist process scenario discovery results. A real wastewater treatment process provided by a domain expert is used as a case study to investigate the effectiveness and validity of the approach. We also use five real-life event logs to compare the performance of the process approach for process scenario discoveries with the commonly used k-means clustering approach. To measure the validity of our results, we take the weighted average fitness, the weighted average precision, and the F1 score. The experiment data show that (1) the proposed approach is able to discover the process scenarios from event logs by incorporating domain knowledge and (2) the process models obtained with the proposed approach have higher fitness, precision, and F1 scores than the models obtained by the commonly used k-means clustering approaches.

Wastewater treatment processes are inherently dynamic due to the large variations in influent wastewater flow rate, weather conditions, concentration,and composition. The utilization of trace clustering techniques in process mining research field is an excellent way to analyze both the execution and confirm the compliance of wastewater treatment processes. However, much of existing trace clustering research has been focused on applying activity names to assist process scenarios discovery without considering other information in event logs. In addition, many existing algorithms commonly used in the literature, such as k-means clustering approach, require prior knowledge about the number of process scenarios existed in the log, which sometimes are not known aprior. This paper presents an approach that uses timing information to assist in discovering process scenarios from event logs in wastewater treatment processes without requiring any prior knowledge about process scenarios. A real wastewater treatment process provided by a domain expert is used as a case study to investigate the effectiveness and validity of the approach. We also use five real-life event logs to compare the performance of the proposed approach for process scenario discoveries with the commonly used k-means clustering approach in terms of model’s harmonic mean of the weighted average fitness and precision, i.e., the F1 score. The experiment data shows that (1) the proposed approach is able to discover the process scenarios from event logs in wastewater treatment domain; (2) the process scenario models obtained with the additional timing information have both higher fitness and precision scores than the models obtained without the timing information.

Process mining aims to extract useful process knowledge and provide valuable insights to better understand, monitor, and improve current business processes. The most critical learning task in process mining is process discovery. Process discovery takes an event log as an input and generates a process model as an output. In the last two decades, processing mining communities have proposed several process discovery algorithms. Many of these algorithms are based on or are extensions of three commonly used process mining algorithms. These algorithms are known as the α algorithm, the Heuristic algorithm and the Inductive algorithm. This study provides an evaluation of these three algorithms using both artificial event logs and real-life event logs. We study the impact of dependency patterns, noise, and complexity. Our work aims to provide clear guidelines for academics or business organizations that are interested in using process mining algorithms to discover their hidden process models and choose the most appropriate process discovery algorithm.

Process mining is a technique for extracting process models from event logs. Event logs contain abundant information related to an event such as the timestamp of the event, the actions that triggers the event, etc. Much of existing process mining research has been focused on discoveries of process models behind event logs. How to uncover the timing constraints from event logs that are associated with the discovered process models is not well-studied. In this paper, we present an approach that extends existing process mining techniques to not only mine but also integrate timing constraints with process models discovered and constructed by existing process mining algorithms. The approach contains three major steps, i.e., first, for a given process model constructed by an existing process mining algorithm and represented as a workflow net, extract a time dependent set for each transition in the workflow net model. Second, based on the time dependent sets, develop an algorithm to extract timing constraints from event logs for each transition in the model. Third, extend the original workflow net into a time Petri net where the discovered timing constraints are associated with their corresponding transitions. A real-life road traffic fine management process scenario is used as a case study to show how timing constraints in the fine management process can be discovered from event logs with our approach.

During the system development process, domain experts and developers often make assumptions about specifications and implementations. However, most of the assumptions being taken for granted by domain experts and developers are too tedious to be documented by them. When these unspecified assumptions are violated in an environment in which the system operates, failures can occur. According to the U.S. Food and Drug Administration (FDA) medical device recall database, medical device recalls caused by software failures are at an all-time high. One major cause of these recalls is violations of unspecified assumptions made in medical systems. Therefore, it is crucial to have tools to automatically identify such unspecified assumptions at an early stage of the systems development process to avoid fatal failures. In this article, we present a tool called Unspecified Assumption Carrier Finder ( UACFinder ) that uses data mining techniques to automatically identify potential syntactic carriers of unspecified assumptions in system design models. The main idea of this tool is based on the observation we obtained from our earlier analysis of software failures in medical device recalls caused by unspecified assumptions. We observed that unspecified assumptions often exist in medical systems through syntactic carriers , such as constant variables , frequently read/updated variables , and frequently executed action sequences . Therefore, we develop the UACFinder to automatically find these potential unspecified assumption syntactic carriers rather than unspecified assumptions themselves. Once the UACFinder identifies the potential unspecified assumption syntactic carriers , domain experts and developers can validate whether these syntactic carriers indeed carry unspecified assumptions. We use a simplified cardiac arrest treatment scenario as a case study to evaluate the UACFinder in mining potential syntactic carriers of unspecified assumptions. In addition, we invite a medical doctor to validate unspecified assumptions carried by the mined syntactic carriers . The case study demonstrates that the UACFinder is effective in helping to identify potential unspecified assumptions from system design models.

Improving patient care safety is an ultimate objective for medical cyber-physical systems. A recent study shows that the patients' death rate can be significantly reduced by computerizing medical best practice guidelines. To facilitate the development of computerized medical best practice guidelines, statecharts are often used as a modeling tool because of their high resemblances to disease and treatment models and their capabilities to provide rapid prototyping and simulation for clinical validations. However, some implementations of statecharts, such as Yakindu statecharts, are priority-based and have synchronous execution semantics which makes it difficult to model certain functionalities that are essential in modeling medical guidelines, such as two-way communications and configurable execution orders. Rather than introducing new statechart elements or changing the statechart implementation's underline semantics, we use existing basic statechart elements to design model patterns for the commonly occurring issues. In particular, we show the design of model patterns for two-way communications and configurable execution orders and formally prove the correctness of these model patterns. We further use a simplified airway laser surgery scenario as a case study to demonstrate how the developed model patterns address the two-way communication and configurable execution order issues and their impact on validation and verification of medical safety properties.

According to the U.S. Food and Drug Administration (FDA) medical device recall database, medical device recalls are at an all-time high. One of the major causes of the recalls is due to implicit assumptions of which either the medical device operating environment does not match, or the device operators are not aware of. In this paper, we present IAFinder (Implicit Assumption Finder), a tool that uses data mining techniques to automatically extract invariants from design models implemented with statecharts. By identifying invariants that are not explicitly specified in the design models, we are able to find implicit assumptions and better facilitate domain experts to validate them and make the validated implicit assumptions explicit. We use a cardiac arrest statechart model as a case study to illustrate the usage of IAFinder in identifying implicit assumptions.

For a cyber-physical system, its execution behaviors are often impacted by human interactive behaviors. However, the assumptions about a cyber-physical systems expected human interactive behaviors are often informally documented, or even left implicit and unspecified in system design. Unfortunately, such implicit human interaction assumptions made by safety critical cyber-physical systems, such as medical cyber-physical systems (M-CPS), can lead to catastrophes. Several recent U.S. Food and Drug Administration (FDA) medical device recalls are due to implicit human interaction assumptions. In this paper, we classify the categories of constraints in human interaction assumptions in the medical domain and develop a mathematical assumption model that allow M-CPS engineers to explicitly and precisely specify assumptions about human interactions. Algorithms are developed to integrate mathematical assumption models with system model so that the safety of the system can be not only validated by both medical and engineering professionals but also formally verified by existing formal verification tools. We use an FDA recalled medical ventilator scenario as a case study to show how the mathematical assumption model and its integration in M-CPS design may improve the safety of the ventilator and M-CPS in general.

Improving effectiveness and safety of patient care is an ultimate objective for medical cyber-physical systems. Many medical best practice guidelines exist in the format of hospital handbooks which are often lengthy and difficult for medical staff to remember and apply clinically. Statechart is an effective tool to model medical guidelines and enables clinical validation with medical staffs. However, some advanced statechart elements could result in high cost, such as low understandability, high difficulty in clinical validation, formal verification, and failure trace back. The paper presents a pattern-based statechart modeling approach for medical best practice guidelines, i.e., model medical guidelines with basic statechart elements and model patterns which are built upon these basic elements. For practical use, we implement the proposed approach based on open-source Yakindu statecharts. We also use a simplified cardiac arrest scenario provided to our team by Carle Foundation Hospital as a case study to validate the proposed approach.

Improving safety of patient care is an ultimate objective for medical systems. Though many medical best practice guidelines exist and are in hospital handbooks, they are often lengthy and difficult for medical professionals to remember and apply clinically. Hence, developing safe and correct medical best practice guideline systems is an urgent need. Many efforts have been made in modeling, clinical validation, model level formal verification of medical best practice guidelines. However, code level verification is also necessary to develop verifiable safe and correct medical guideline systems. The paper presents an approach to transform safety properties specified in verifiable medical guideline models to JavaMOP runtime monitor and specify JavaMOP monitors to runtime monitor these safety properties during execution of Java code generated from validated and verified statechart models. We use a simplified version of a cardiac arrest scenario provided by Carle Foundation Hospital as a case study to validate the proposed approach.

Implicit physical environment assumptions made by safety critical cyber-physical systems, such as medical cyber-physical systems (M-CPS), can lead to catastrophes. Several recent U.S. Food and Drug Administration (FDA) medical device recalls are due to implicit physical environment assumptions. In this paper, we develop a mathematical assumption model and composition rules that allow M-CPS engineers to explicitly and precisely specify assumptions about the physical environment in which the designed M-CPS operates. Algorithms are developed to integrate the mathematical assumption model with system model so that the safety of the system can be not only validated by both medical and engineering professionals but also formally verified by existing formal verification tools. We use an FDA recalled medical ventilator scenario as a case study to show how the mathematical assumption model and its integration in M-CPS design may improve the safety of the ventilator and M-CPS in general.

Improving effectiveness and safety of patient care is an ultimate objective for medical cyber-physical systems. A recent study shows that the patients' death rate can be reduced by computerizing medical guidelines [20]. Most existing medical guideline models are validated and/or verified based on the assumption that all necessary medical resources needed for a patient care are always available. However, the reality is that some medical resources, such as special medical equipment or medical specialists, can be temporarily unavailable for an individual patient. In such cases, safety properties validated and/or verified in existing medical guideline models without considering medical resource availability may not hold any more.

As technology advances, medical devices are playing increasingly more important roles in patient care. Unfortunately, based on the U.S. Food and Drug Administration (FDA) data, medical device recalls are at an all time high. One of the major causes of the recalls is due to defective software. In fact, one in every three medical devices that use software for operation has been recalled because of failures in the software itself. Unlike traditional software, software-based medical devices have specific domain fault modes, and these fault modes have been not addressed in software design literature, such as dosage calculation fault. In this paper, we first present a process that collects software-related medical device recalls from the FDA database. Collecting all software-related medical device recalls is an effort that needs the support and contributions from a large research, industrial, and medical community, To facility such effort, we have developed a web-based platform for different users to contribute and share new software-related medical device recalls into the collection. Second, we analyze one hundred software-related recalls that we have collected from the FDA database. Our analysis reveals that there are four major categories of software failures in medical device recalls and implicit assumptions made by medical device manufacturers are among one of the leading causes in medical device recalls. Last, we present an approach for implicit assumption management in medical cyber-physical system designs.

Researches in real-time scheduling often assume that the performance of a computing resource does not change overtime. However, as system softwares and system architectures become increasingly complex, resource performance degradation over time becomes more evident. In this paper, we study the schedulability of a hard real-time task set on a resource which has performance degradation over time with a known pattern and use both cold and warm periodic rejuvenations as countermeasures. Such resource model is referred to as P2D-resource model for performance degradation and periodic rejuvenation with dual-levels. In this paper, we study (1) the formal specification of the P2D-resource model, (2) P2D-resource supply analysis, and (3) task set utilization bounds of a P2D-resource under Earliest Deadline First (EDF) and Rate Monotonic (RM) scheduling policies.

Cloud bursting is one of the key research topics in the cloud computing communities. A well designed cloud bursting module enables private clouds to automatically launch virtual machines (VMs) to public clouds when more resources are needed. One of the main challenges in developing a cloud bursting module is to decide when and where to launch a VM so that all resources are most effectively and efficiently utilized and the system performance is optimized. However, based on system operational data obtained from FermiCloud, a private cloud developed by the Fermi National Accelerator Laboratory for scientific workflows, the VM launching overhead is not a constant. It varies with physical resource utilization, such as CPU and I/O device utilizations, at the time when a VM is launched. Hence, to make judicious decisions as to when and where a VM should be launched, a VM launching overhead reference model is needed. In this paper, we first develop a VM launching overhead reference model based on operational data we have obtained on FermiCloud. Second, we apply the developed reference model on FermiCloud and compare calculated VM launching overhead values based on the model with measured overhead values on FermiCloud. Our empirical results on FermiCloud indicate that the developed reference model is accurate. We believe, with the guidance of the developed reference model, efficient resource allocation algorithms can be developed for cloud bursting process to minimize the operational cost and resource waste.

The periodic task set assignment problem in the context of multiple processors has been studied for decades. Different heuristic approaches have been proposed, such as the Best-Fit (BF), the First-Fit (FF), and the Worst-Fit (WF) task assignment algorithms. However, when processors are not dedicated but only periodically available to the task set, whether existing approaches still provide good performance or if there is a better task assignment approach in the new context are research problems which, to our best knowledge, have not been studied by the real-time research community. In this paper, we present the Best-Harmonically-Fit (BHF) task assignment algorithm to assign periodic tasks on multiple periodic resources. By periodic resource we mean that for every fixed time interval, i.e., the period, the resource always provides the same amount of processing capacity to a given task set. Our formal analysis indicates that if a harmonic task set is also harmonic with a resource's period, the resource capacity can be fully utilized by the task set. Based on this analysis, we present the Best-Harmonically-Fit task assignment algorithm. The experimental results show that, on average, the BHF algorithm results in$53.26$,$42.54$, and$27.79$percent higher resource utilization rate than the Best-Fit Decreasing (BFD), the First-Fit Decreasing (FFD), and the Worst-Fit Decreasing (WFD) task assignment algorithms, respectively; but comparing to the optimal resource utilization rate found by exhaustive search, it is about$11.63$percent lower.

For a time-sensitive application, the usefulness of its end results (also called the application's accrued utility value in the paper) depends on the time when the application is completed and its results are delivered. In this paper, we address the accrued utility value maximization problem for narrow parallel and time-sensitive applications. We first consider the problem in the context of a discrete time domain and present the Spatial-Temporal Interference Based (STIB) scheduling algorithm. We formally prove that the STIB algorithm is a 2-approximation algorithm. Second, we extend our work to a continuous time domain and present a heuristic scheduling algorithm, i.e., the Continuous Spatial-Temporal Interference Based (STIB-C) algorithm to maximize the system's total accrued utility value when the system operates in a continuous time domain. The extensive empirical evaluations reveal that: (1) in a discrete time domain, the systems' total accrued utility values obtained through the STIB algorithm are consistent with the theoretic bound, i.e., they never go below 50 percent of the optimal value. In fact, on average, the STIB algorithm can achieve over 92.5 percent of the optimal value; (2) compared to other scheduling policies listed in the literature, the developed STIB and STIB-C algorithms have clear advantages in terms of the system's total accrued utility value and the profitable application ratio. In particular, in terms of the system's total accrued utility value, both the STIB and the STIB-C algorithms achieve as much as six times for both the First Come First Come Serve(FCFS) with backfilling algorithm and the Gang Earliest Deadline First (EDF) algorithm, and 4.5 times for the 0-1 Knapsack based scheduling algorithm. In terms of the profitable application ratio, both the STIB and the STIB-C algorithms obtain as much as four times for both the FCFS with backfilling algorithm and the Gang EDF algorithm, and two times for the 0-1 Knapsack based scheduling algorithm.

In this paper, we address the resource and virtual machine instance hour minimization problem for directed-acyclic-graph based deadline constrained applications deployed on computer clouds. The allocated resources and instance hours on computer clouds must: (1) guarantee the satisfaction of a deadline constrained application's end-to-end deadline; (2) ensure that the number of virtual machine (VM) instances allocated to the application is minimized; (3) under the allocated number of VM instances, determine application execution schedule that minimizes the application's makespan; and (4) under the decided application execution schedule, determine a VM operation schedule, i.e., when a VM should be turned on or off, that minimizes total VM instance hours needed to execute the application. We first give lower and upper bounds for the number of VM instances needed to guarantee the satisfaction of a deadline constrained application's end-to-end deadline. Based on the bounds, we develop a heuristic algorithm called minimal slack time and minimal distance (MSMD) algorithm that finds the minimum number of VM instances needed to guarantee the application's deadline and schedules tasks on the allocated VM instances so that the application's makespan is minimized. Once the application execution schedule and the number of VM instances needed are determined, the proposed VM instance hour minimization (IHM) algorithm is applied to further reduce the instance hours needed by VMs to complete the application's execution. Our experimental results show that the MSMD algorithm can guarantee applications' end-to-end deadlines with less resources than the HEFT [32], MOHEFT [16], DBUS [9], QoS-base [40] and Auto-Scaling [25] heuristic scheduling algorithms in the literature. Furthermore, under allocated resources, the MSMD algorithm can, on average, reduce an application's makespan by 3.4 percent of its deadline. In addition, with the IHM algorithm we can effectively reduce the application's execution instance hours compared with when IHM is not applied.

The increased resource sharing on multi-core platforms has posed significant challenges on the predictability of real-time systems. Cache memory partitioning has proven to be one of the most effective methods to improve the predictability and also the schedulability of real-time systems. In this paper, we study how to allocate cache memory of a multi-core platform when scheduling fixed-priority hard real-time tasks. As the bounded worst-case execution time (WCET) of a real-time task varies with its cache allocation, the challenges of this problem are twofold: how to judiciously allocate the cache memory among all real-time tasks and how to map real-time tasks to each core to improve the schedulability. To address these challenges, we develop an approach that takes into consideration not only the WCET variations with cache allocations but also the task period relationship and thus can significantly improve the schedulability of real-time tasks. Our simulation results, based on the SPEC CPU2000 benchmarks suite, show that our approach can increase the schedulability of real-time tasks up to four times when compared to other similar scheduling mechanisms.

Most schedulability analyses in the literature assume that the performance of computing resource does not change over time. However, due to ever increased complexity of computer systems, software aging issues become more difficult, if not impossible, to eradicate. Hence, the assumption that computing resource has a constant performance in its entire lifetime does not hold in real world long-standing systems. In this paper, we study real-time task schedulability under a resource model that the resource's performance degrades with a known degradation function and the resource is periodically rejuvenated. The resource model is referred to as P2-resource model for performance degradation and periodic rejuvenation. We address three real-task schedulability related questions under the P2-resource model, i.e., (1) resource supply bounds of the P2-resource, (2) task set utilization bounds under Earliest Deadline First (EDF) and Rate Monotonic (RM) scheduling policies, respectively, and (3) experimentally study the tightness of the bounds developed, and the impact of resource degradation rate, rejuvenation period, and rejuvenation cost on the bounds.

Fermi Cloud is a private cloud developed by the Fermi National Accelerator Laboratory for scientific workflows. The Cloud Bursting module of the Fermi Cloud enables the Fermi Cloud, when more computational resources are needed, to automatically launch virtual machines to available resources such as public clouds. One of the main challenges in developing the cloud bursting module is to decide when and where to launch a VM so that all resources are most effectively and efficiently utilized and the system performance is optimized. However, based on Fermi Cloud's system operational data, the VM launching overhead is not a constant. It varies with physical resource (CPU, memory, I/O device) utilization at the time when a VM is launched. Hence, to make judicious decisions as to when and where a VM should be launched, a VM launch overhead reference model is needed. The paper is to develop a VM launch overhead reference model based on operational data we have obtained on Fermi Cloud and uses the reference model to guide the cloud bursting process.

Web applications grow tremendously in both scale and scope, the application patterns turn to be more and more sophisticated. It is important but challenging for service providers to lower the operational costs without degrading user experiences, especially in the case where a service provider's profit is closely related to the user experience (e.g. response time.) In this paper, we study the problem of efficiently scheduling multi-tier time sensitive applications on distributed computing platforms with respect to the user's Quality of Service (QoS) requirements. The efficiency refers to the QoS satisfaction with low average response times. The service provider must ensures that service requests be served successfully before end-to-end deadlines with certain probabilities. To solve this problem, we propose an approach to judiciously assign a deadline for each service tier. An application request is dropped if any one of its services misses its deadline. Our simulation results demonstrate that our approach can statistically guarantee the required QoS more efficiently than the other widely applied methods (e.g. acceptance control, first-come-first-serve, deterministic sub deadline assignment, etc.) irrespective of whether the resources are shared or not by multiple different applications.

Distributed soft real-time applications often involve multiple jobs that are executed on different processing units. Hence, resource competitions among these applications can be on any processing unit in the system. However, due to distributed nature of these applications, each processing unit may not have the knowledge about the workload on other processing units. Therefore, scheduling decisions made by individual processing units about their local job execution orders may not be optimal for the applications to which the jobs belong with respect to meeting the applications' end-to-end deadlines. In this paper, we first introduce a metric to measure, at a local processing unit, the risk of a distributed soft real-time application missing its end-to-end deadline. Second, based on the metric, we develop a local deadline assignment algorithm, i.e., the delay-impact-based (DIB) local deadline assignment algorithm. With the DIB algorithm, distributed processing units can independently schedule their local job sets based on the assigned job deadlines with maximized successful ratio of meeting distributed real-time applications' end-to-end deadlines. We empirically compare the DIB algorithm with three commonly used local deadline assignment algorithms, i.e., the OLDA, Pure, and Norm algorithms. The experimental results show that the DIB algorithm has clear advantage over the OLDA, Pure, and Norm approaches — it results in up to 50%, 35%, and 35% higher successful ratio than the OLDA, Pure, and Norm approaches with respect to meeting application's end-to-end deadlines, respectively. Furthermore, for those applications that do miss their end-to-end deadlines, the application execution delay ratio resulted by the DIB algorithm is also up to 300%, 50%, and 150% smaller comparing to the other three approaches.

For a time-sensitive application, the usefulness or the quality of the application's end result depends on the time when the result is delivered, or when the application is completed. A Time Utility Function (TUF) is often used to represent the dependency between an application's accrued value and its completion time. For parallel and time-sensitive applications, each application has multiple tasks that must be executed concurrently in order to produce a result. Therefore, their execution occupies resources in two dimensions: spatial, i.e., the number of processing units needed to support concurrent tasks, and temporal, i.e., time duration needed to complete the application. Because of the parallelism and time-sensitive features of the applications, the execution interference among parallel and time-sensitive applications can be both in spatial and temporal domains. In this paper, we first introduce a metric to measure the spatial-temporal interference on applications' accrued values. Second, based on the metric, we develop a scheduling algorithm, i.e., the Discounting Spatial-Temporal Interference (DSTI) scheduling algorithm, to maximize system's total accrued utility value for a given set of parallel and time-sensitive applications. Our simulation results show that the proposed DSTI algorithm results in close to optimal solutions and also has clear advantage over existing approaches in the literature in terms of system total accrued utility values and profitable application ratio. It accrues up to 164%, 150%, and 97% more system value, and up to 21%, 35%, and 18% higher profitable application ratio than the Gang EDF, the FCFS with backfilling, and the 0-1 Knapsack based scheduling algorithms, respectively.

The performance of the Hadoop Distributed File System (HDFS)decreases dramatically when handling interaction-intensive files, i.e., files that have relatively small size but are accessed frequently. The paper analyzes the cause of throughput degradation issue when accessing interaction-intensive files and presents an enhanced HDFS architecture along with an associated storage allocation algorithm that overcomes the performance degradation problem. Experiments have shown that with the proposed architecture together with the associated storage allocation algorithm, the HDFS throughput for interaction-intensive files increase 300% in average with only a negligible performance decrease for large data set tasks.

Many-core Network-on-Chip (NoC) processors are emerging in broad application areas, including those with timing requirements, such as real-time and multimedia applications. Typically, these processors employ core-level backup to improve yield. However, when defective cores are replaced by backup ones, the NoC topology changes. Consequently, a fine-tuned application based on timing parameters given by one topology may not meet the expected timing behavior under the new one. We first develop a metric to measure timing similarity of an application on different NoC topologies and then propose mixed binary quadratic programming and greedy algorithms to reconfigure a defect-tolerant many-core NoC.

System reliability has always been a challenging issue for many systems. In order to achieve high reliability, redundancy and voting schemes are often used to tolerate unintentional component failures. For unintentional failures caused by, for instance, normal wear-outs, hardware failures, or software bugs, etc., adding more redundancies often improves a system's reliability. However, when attack-caused failures exist, the number of redundant components and the number of participating voting entities may not be positively proportional to system reliability. In this paper, we study system reliability and system defense strategies when the system is under rational attacks. In particular, we analyze how defense and attack strategies may impact system reliability when both the defender and attacker are given a fixed amount of resources that can only be used for adding camouflaging components or enhancing existing components' cyber protection by defenders, or selecting a subset of components to attack by attackers, respectively. We also present an algorithm to decide the optimal defense strategy in fighting against rational attacks.

Cloud computing is changing the infrastructure upon which scientific computing depends from supercomputers and distributed computing clusters to a more elastic cloud-based structure. The service-oriented focus and elasticity of clouds can not only facilitate technology needs of emerging business but also shorten response time and reduce operational costs of traditional scientific applications. Fermi National Accelerator Laboratory (Fermilab) is currently in the process of building its own private cloud, FermiCloud, which allows the existing grid infrastructure to use dynamically provisioned resources on FermiCloud to accommodate increased but dynamic computation demand from scientists in the domains of High Energy Physics (HEP) and other research areas. Cloud infrastructure also allows to increase a private cloud's resource capacity through "bursting" by borrowing or renting resources from other community or commercial clouds when needed. This paper introduces a joint project on building a cloud federation to support HEP applications between Fermi National Accelerator Laboratory and Korea Institution of Science and Technology Information, with technical contributions from the Illinois Institute of Technology. In particular, this paper presents two recent accomplishments of the joint project: (a) cloud bursting automation and (b) load balancer. Automatic cloud bursting allows computer resources to be dynamically reconfigured to meet users' demands. The load balance algorithm which the cloud bursting depends on decides when and where new resources need to be allocated. Our preliminary prototyping and experiments have shown promising success, yet, they also have opened new challenges to be studied.

The advent of cloud systems has spurred the emergence of an impressive assortment of Internet services. Recent pressures on enhancing the profitability by curtailing surging dollar costs on energy have posed challenges to, as well as placed a new emphasis on, designing energy-efficient request dispatching and resource management algorithms. What further adds to the design challenge is the highly diverse nature of Internet service requests in terms of Quality-of-Service (QoS) constraints and business values. Nonetheless, most of the existing job scheduling and resource management solutions are for a single type of request and are profit oblivious. They are unable to reap the benefit of multi-service profit-aware algorithm designs. In this paper, we consider a cloud service provider operating geographically distributed data centers in a multi-electricity-market environment, and propose an energy-efficient, profit-and cost-aware request dispatching and resource allocation algorithm to maximize a service provider's net profit. We formulate the net profit maximization issue as a constrained optimization problem, using a unified task model capturing multiple cloud layers (e.g., SaaS, PaaS, IaaS.) The proposed approach maximizes a service provider's net profit by judiciously distributing service requests to data centers, powering on/off an appropriate number of servers, and allocating server resources to dispatched requests. We conduct extensive experiments to validate our proposed algorithm. Results show that our proposed approach can improve a service provider's net profit significantly.

In distributed real-time systems, when resource cannot meet workload demand, some jobs have to be removed from further execution. The decision as to which job to remove directly influences the system computation efficiency, i.e., the ratio between computation contributed to successful completions of real-time jobs and total computation contributed to the execution of jobs that may or may not be completed. The paper presents two job removal policies which aim at maximizing system's computation efficiency for distributed real-time applications where the applications' end-to-end deadlines must be guaranteed. Experiments based on benchmark applications generated by TGFF [1] are conducted and compared with recent work in the literature. The results show clear benefits of the developed approaches - they can achieve as much as 20% computation efficiency improvement.

In this paper, we study the energy minimization problem for a frame-based real time system with guaranteed reliability using the checkpointing technique. We formally prove that executing a real time task set with a uniform frequency, or neighboring frequencies if the desired frequency is not available, not only optimizes its energy consumption but also achieves maximal reliability. Based on the theoretic conclusion, we further develop a Dynamic Voltage Frequency Scaling (DVFS) and checkpoint allocation strategy for a task set to guarantee both reliability and deadline constraints but with minimal energy consumption. The proposed strategy has very small frequency switching overhead as no more than one frequency change is needed for the entire task set execution and thus is particularly effective for processors with large frequency switching overhead. We further empirically compare our approach with recent work published in the literature. The experimental results show that the proposed approach can reduce as much as 15% energy consumption.

As computers and Internet technology advance, many time-dependent applications, such as mobile navigation and online gaming, are emerging. Time-dependent applications are associated with a pair of time-dependent functions representing accrued gain at the time when tasks complete or accrued cost when tasks fail to complete, respectively. For systems that provide time-dependent services, the optimization goal is to maximize the system profit when both potential gain and potential cost exist for each request the system accepts. This paper presents two scheduling algorithms, prediction-based highest gain density first (PHGDF) and iterative PHGDF (iPHGDF) scheduling algorithms with the objective to maximize the system's total accrued profit. Simulation results provide clear evidence that, with respect to the system total accrued profit, the proposed PHGDF and iPHGDF algorithms have advantages over other commonly used scheduling algorithm, such as the Earliest Deadline First (EDF), the Generic Utility Scheduling (GUS) and the Profit and Penalty aware scheduling (PP-aware) algorithms.

Homogeneous manycore processors are emerging in broad application areas, including those with timing requirements, such as real-time and embedded applications. Typically, these processors employ Network-on-Chip (NoC) as the communication infrastructure and core-level redundancy is often used as an effective approach to improve the yield of manycore chips. For a given application's task graph and a task to core mapping strategy, the traffic pattern on the NoC is known a priori. However, when defective cores are replaced by redundant ones, the NoC topology changes. As a result, a fine-tuned program based on timing parameters given by one topology may not meet the expected timing behavior under the new one. To address this issue, a timing similarity metric is introduced to evaluate timing resemblances between different NoC topologies. Based on this metric, a Hungarian method based algorithm is developed to reconfigure a defect-tolerant manycore platform and form a unified application specific virtual core topology of which the timing variations caused by such reconfiguration are minimized. Our case studies indicate that the proposed metric is able to accurately measure the timing differences between different NoC topologies. The standard deviation between the calculated difference using the metric and the difference obtained through simulation is less than 6.58%. Our case studies also indicate that the developed Hungarian method based algorithm using the metric performs close to the optimal solution in comparison to random defect-redundant core assignments.

As transistor's feature size continues to scale down into the deep sub-micron domain, IC chip performance variation caused by manufacturing process becomes un-negligible and can cause significant discrepancies between an application's nominal design and its actual realization on individual manycore platforms. In this paper, we study the problem on how to reduce the total schedule length of a task graph when realizing its nominal design on individual Network-on-Chip(NoC) based many-core platform with faulty cores. Different from traditional approaches to re-define the mapping/scheduling decisions in the nominal design, our methods judiciously mirror the physical architecture of each individual platform to the logical platform, based on which the nominal design is conducted. To facilitate the phyical/logic architecture virtualization, we develop a performance metric based on the opportunity cost, a concept borrowed from the economics field. Three virtualization heuristics are presented in this paper. Our experimental results show that the proposed approach can achieve up to 30% with an average 15% performance improvement by taking advantage of the heterogeneity of each individual platform.

For many embedded systems, different real-time applications are consolidated to the same hardware platform to meet the growing demand for diverse functionalities. Due to functionality differences, the values that different applications contribute to the system may not be the same. When system resources are limited and not all applications can be executed with guaranteed QoS, decisions have to be made as to which applications should be selected and how their tasks are deployed on available processors so that the system value is maximized and all the selected applications meet their deadlines. However, making the optimal decision for the application selection and task deployment (ASTD) problem is NP-hard. In this paper, we present a genetic algorithm (GA) based approach for the ASTD problem. We experimentally compare the performance of GA-based approach with the optimal approach chosen by enumerating all possible choices on a small scale, and with other heuristic approaches existed in the literature on a large scale. The results show that the system value obtained by the GA-based approach is close to the optimal value and can be twice as large as the value obtained by other heuristic approaches.

This paper transforms sequential power flow problem to a parallel problem and solves it on GPU. In particular, we implement parallel Gauss-Seidel solver, Newton-Raphson solver, and P-Q decoupled solver using CUDA (Compute Unified Device Architecture) on GPU. The aim is to investigate the performance of the three different parallel power flow solvers. We use four IEEE standard power systems and one actual running power system from Shang dong Province as the test cases when comparing the speedups that a GPU system can provide. The results show that Newton-Raphson solver has the best speedup when it is operated on GPU, Gauss-Seidel solver performs the worst, and P-Q decoupled solver is in the middle. The test results also indicate that when the size of the system is small, GPU does not seem to have advantages over CPU from computation time perspective. However, as the size of the system increases, the advantages of GPU becomes more clear. For instance, when the system has close to one thousand bus counts, the GPU can provide as high as over fifty-three times speedup.

As computer and Internet technology continue to advance, real-time online services are emerging. Different from traditional real-time applications for which the scheduling objective is to meet task deadlines, the optimization goal for online service systems is to maximize profit obtained through providing timely services. For this class of applications, there are two distinctive characteristics. First, tasks are associated with a pair of time dependent functions representing accrued profit when completed before their deadlines and accrued penalty otherwise, respectively. Second, the service requests or tasks arrive aperiodically with execution time varying in a wide range. This paper presents a novel scheduling method and related analysis for such applications. Two scheduling algorithms, i.e., the nonpreemptive and preemptive Profit and Penalty aware (PP-aware) scheduling algorithms, are proposed with an objective to maximize system's total accrued profit. Our simulation results clearly demonstrate the advantages of the proposed algorithms, with respect to the system total accrued profit, over other commonly used scheduling algorithms, such as Earliest Deadline First (EDF) and Utility Accrual (UA) algorithms.

Voting algorithms are often used to improve a system's reliability through fault tolerance. However, when both the reliability of individual voters and the existence of rational attackers are taken into consideration, the number of voters that participate in an actual voting process determines the fault-and-attack tolerance performance of voting algorithms. In this paper, we are to find an optimal voting strategy (i.e., the optimal number of participating voters) against rational attackers whose goal is to defect the system by strategically compromising individual voters across the system. We model the problem of deciding the number of participating voters against rational attackers as a two-person zero-sum game problem and provide solutions based on the results from this well-known game problem. A set of experiments are performed to illustrate the voting strategy's performance in the presences of rational attackers.

Mission critical systems often operate for limit time durations. For these systems, we subscribe to the notion that provisioning of security can be based on the expected duration of a system's mission. In this paper, we present a simple and safe K-variant approach to improve time-based mission critical systems' attack-survivability and provide formal analysis about K-variant system's attack survivability under M memory-based attack attempts. Our theoretical analysis supported by extensive simulations and a case study provide good evidences that the proposed approach may be in improving system's attack-survivability.

Real-time systems are systems in which their timing behaviors must satisfy a specified set of timing constraints and they often operate in a real-world environment with scarce resources. As a result, the actual runtime performance of these systems may deviate from the design, either inevitably due to unpredictable factors or by intention in order to improve system’s other Quality-of-Service (QoS) properties. In this article, we first introduce a new metric, timing constraint set similarity , to quantify the resemblance between two different timing constraint sets. Because directly calculating the exact value of the metric involves calculating the size of a polytope which is a # P -hard problem, we instead introduce an efficient method for estimating its bound. We further illustrate how this metric can be exploited for improving system predictability and for evaluating trade-offs between timing constraint compromises and the system’s other QoS property gains.

Topology virtualization techniques are proposed for NoC-based many-core processors with core-level redundancy to isolate hardware changes caused by on-chip defective cores. Prior work focuses on homogeneous cores with symmetric performance and optimizes on-chip communication only. However, core-to-core performance asymmetry due to manufacturing process variations poses new challenges for constructing virtual topologies. Lower performance cores may scatter over a virtual topology, while operating systems typically allocate tasks to continuous cores. As a result, parallel applications are probably assigned to a region containing many slower cores that become bottlenecks. To tackle the above problem, in this paper we present a novel performance-asymmetry-aware reconfiguration algorithm Bubble-Up based on a new metric called core fragmentation factor (CFF). Bubble-Up can arrange cores with similar performance closer, yet maintaining reasonable hop distances between virtual neighbors, thus accelerating applications with higher degree of parallelism, without changing existing allocation strategies for OS. Experimental results show its effectiveness.

In this paper, we introduce a novel utility accrual scheduling algorithm for real-time cloud computing services. The real-time tasks are scheduled non-preemptively with the objective to maximize the total utility. The most unique characteristic of our approach is that, different from the traditional utility accrual approach that works under one single time utility function (TUF), we have two different TUFs-a profit TUF and a penalty TUF-associated with each task at the same time, to model the real-time applications for cloud computing that need not only to reward the early completions but also to penalize the abortions or deadline misses of real-time tasks. Our experimental results show that our proposed algorithm can significantly outperform the traditional scheduling algorithms such as the Earliest Deadline First (EDF), the traditional utility accrual scheduling algorithm and an early scheduling approach based on the similar model.

Real-time and embedded applications often involve different types of timing constraints, such as precedence constraints and real-time constraints. As real-time and embedded applications further advance, new timing constraint types are emerging as well. Recent research on interval-based timing constraints is an example. Thus, it is important to have a uniformed timing constraint representation so that a generalized approach can be developed to analyze the variant constraint types. A semiring-based timing constraint model is introduced to generalize the representations of different constraint types. Under this model, we develop an algorithm to check the satisfaction feasibility for a given set of semiring-based timing constraints. This algorithm provides better performance in the average case as compared to applying the Bellman-Ford algorithm directly on the constraint set. In addition, for a set of feasible semiring-based timing constraints, event occurrence points that satisfy the constraint set form a (hyperdimension) feasible region. For the given two sets of timing constraints, we develop a necessary and sufficient condition to testify whether the two constraint sets' feasible regions have an inclusion relation. If one feasible region is included in the other, we know that the real-time event occurrences that satisfy the included constraint set will necessarily satisfy the including set.

For soft real-time systems, timing constraints are not as stringent as those in hard real-time systems: some constraint violations are permitted as long as the amount of violation is within a given limit. The allowed flexibility for soft real-time systems can be utilized to improve system's other quality-of-service (QoS) properties, such as energy consumption. One way to enforce constraint violation limit is to allow an expansion of timing constraint feasible region, but restrict the expansion in such a way that the relaxed constraint feasible region sufficiently resembles the original one. In this paper, we first introduce a new metric, constraint set similarity, to quantify the resemblance between two different timing constraint sets. Because directly calculating the exact value of the metric involves calculating the size of a polytope which is a #P-hard problem, we instead introduce an efficient method for estimating its bound. We further discuss how this metric can be exploited for evaluating trade-offs between timing constraint compromises and system's other QoS property gains. We use energy consumption reduction as an example to show the application of the proposed metric.

Unlike general purpose systems, distributed and embedded control systems, such as power grid control systems and water treatment systems, etc., generally have a 24x7 availability requirement. Hence, upgrading or adding new cyber protection features into these systems in order to sustain them when faults caused by cyber attacks occur, is often difficult to achieve and inhibits the evolution of these systems into a cyber environment. In this paper, we present a solution for extending the capabilities of existing systems while simultaneously maintaining the stability of the current systems. An externalized survivability management scheme based on the observe-reason-modify paradigm is applied, which decomposes the cyber attack protection process into three orthogonal subtasks: observation, evaluation and protection. This architecture provides greater flexibility and has an evolvability attribute - it can utilize emerging techniques; yet requires either minimal modifications or even no modifications whatsoever to the controlled infrastructures. The approach itself is general and can be applied to a broad class of observable systems.

With the advent of multicore processors, increasingly more attention is devoted to building concurrent applications capable of fully utilizing the capabilities of these new processors. Unfortunately, in most existing application models, concurrency is not uniformly and externally expressed. The result is that concurrency and thread management are hidden within objects or components and intermixed with their functionalities. In this paper, we present the actor, role and coordinator (ARC) model for concurrent and possibly distributed applications. The ARC uses single-threaded asynchronous sequential objects called actors to denote units of concurrency and computation. Special actors, called roles and coordinators, are used to externally manage the coordination among concurrent computational actors. By externalizing concurrency and separating its coordination from functional behaviors we introduce high level abstractions, increase software reusability and, more importantly, make inherently complicated concurrent applications easier to develop, maintain and reason about in multicore and multi-computer environments.

In real-time distributed systems, it is often difficult to timestamp an event with a point value. Hence, constraints based on intervals are more realistic. However, when a constraint is extended from point-based to interval-based, its satisfaction is not a simple Boolean value; instead, a satisfaction probability is associated with the constraint. We study the satisfaction probability of interval- based timing constraints when event occurrence times are nonuniformly distributed in given time intervals. An algorithm is developed to derive implicit constraints from a set of given interval-based constraints. Our study shows that there are bounds for certain constraint configurations. These analytical results are further applied in two application domains in which constraints are based on single and composite event models, respectively.

In real-time environment, data usually has a lifespan associated with it. The semantics and the importance of the data depend on the time when data is utilized. Hence, the process of getting a consensus data from a group of replicated units must not take longer time than the lifespan of the data. However, in real environments, every unit, faulty or non-faulty, may encounter delays when processing and sending their data which inevitably increases the time of acquiring a consensus. The latency for obtaining a valid data hence depends not only on the time when individual voters make their votes, but also on the accuracy and credibility of the votes. Thus, a new metric, i.e. credibility function, need be taken into account in evaluating expected time and deciding replications. This paper presents analytical solutions for expected time under different voting schemes when dependable data can be obtained. We also show that if not all voters are truthful, adding more replications does not improve much on the time of obtaining valid results.

In real-time environment, data usually has a lifespan associated with it. The semantics and the importance of the data depend on the time when data is utilized. Hence, the process of getting a consensus data from a group of replicated units must not take longer time than the lifespan of the data. However, in real environment, every unit, faulty or non-faulty, may encounter delays when processing and sending their data which inevitably increases the time of acquiring a consensus. The latency for obtaining a valid data hence depends not only on the time when individual replicas make their votes, but also on the accuracy and credibility of the votes. Thus, a new metric, i.e. a credibility function, needs to be taken into account when evaluating expected time and deciding upon data replications. This paper presents analytical solutions for the expected time when dependable data can be obtained under different voting schemes. We show that if not all replicas are truthful, increasing replication does not reduce the time for obtaining valid results. When different types of resources are used to ensure the quality of the data, we show that the allocation of the resource plays an important role in satisfying both data availability and consistency constraints. We further demonstrate that when point-based constraints may be intrinsically impossible to satisfy, a more general interval-based constraint can be used to obtain statistical solutions

One of the main characteristics of open distributed embedded systems is that the involved entities are often very dynamic—different individual entities may join or leave the systems frequently. Therefore, systems built of these dynamic entities must be runtime reconfigurable. In addition, large classes of open embedded systems often have high availability and dependability requirements. However, the openness makes these requirements more difficult to achieve and the system more vulnerable to attacks. This article presents a coordination model, the Actor, Role and Coordinator (ARC) model, that aims to support reconfigurability and fault localization for open distributed embedded software systems. In particular, the actor model is used to model concurrent embedded entities, while the system's reconfigurability and dependability requirements are encapsulated within coordination objects: roles and coordinators, and are achieved through coordination among the actors. Roles, as a key thrust in the ARC model not only represent an abstraction for a set of behaviors shared by a group of actors so that reconfiguration within the roles becomes transparent to entities outside the roles, but also assume coordination responsibilities among the member actors. The article also argues from both analytical and empirical perspectives that with the support of the role, faults can be localized within actors, and actor level reconfiguration becomes transparent to the system.

This paper presents a software architecture that ensures system dependability through external coordination. Under this architecture, a distributed system is decomposed into two types of entities, i.e., computational components and coordinators. The system's computational functionalities are carried out by computational components, whereas coordinators are to coordinate these computational components to respect the system's non-functional requirements, such as reliability constraints. Coordination in the system is done implicitly through intercepting, rerouting and suppressing communications between components. Additionally, roles are introduced into the system to bridge the connection between components and coordinators. Roles abstract the non-functional behaviors shared by computational components. Thus role-based coordination is more scalable than individual component-based coordination. Additionally, the dynamicity of components is concealed from the coordinators by the roles. A proof of concept implementation is built on top of the Actor Architecture, a middleware for distributed systems based on the Actor model by G. Aghal et al. (1997), The results show that not only such separation is feasible, but also that the architecture allows us to better control the dependability of the system. Finally, the application developed based on the proposed model is more modularized and consequently more reusable

Separation of concerns is one of the main tenets of software engineering - allowing developers to reason about software systems in sensible portions, regardless which phase of the lifecycle they are working in. Many researchers in software engineering are actually in the field of aspect-orientation without realizing it.

We apply interval-based timing constraint satisfaction probability results to predict timing constraint violations in real-time embedded system with a known hardware transient failure model. A previous study indicated that hardware transient failures follow a Poisson distribution with an average failure arrival rate lambda. Under this model, the distribution of time intervals between successive failures follows an exponential distribution with the same parameter lambda. Our goal is to use the statistical transient failure models to calculate the earliest time at which we can predict, with a determined level of confidence, that a given timing constraint may be violated. This earlier prediction provides time-critical systems with valuable time before the deadline is reached to adapt themselves, and hence, to minimize possible negative impacts caused by timing constraint violations

We present a coordination language and its semantics for specification and implementation of object-oriented real-time systems. Real-time systems operate under real-time constraints, and our language supports expression thereof. In our language, a system is modeled by two separate but complementary descriptions: A collection of objects define the system's structure and functional behavior and a set of interaction constraints define how these objects may interact. Our language thereby supports development of real-time systems by enabling objects build in isolation or re-used from other systems to be composed via interaction constraints. We use the Actor model to describe objects and the concept of real-time synchronizers to describe interaction constraints. Our model is accompanied by a formal semantics that precisely defines what real-time constraints means, and what constitutes a program's correct real-time behaviors. The semantics defines how the system may evolve in the real-time domain, and what progress guarantees the language makes. We briefly discuss implementation problems and potential solutions.