187377
Efficiently tolerating failures in asynchronous real-time distributed systems
We present a proactive resource allocation algorithm, called BEA, for fault-tolerant asynchronous real-time distributed systems. BEA considers an application model where transnode application timeliness requirements are expressed using benefit functions, and anticipated workload during future time intervals are expressed using adaptation functions. Furthermore, BEA considers an adaptation model where subtasks of application tasks are replicated at run-time for tolerating failures as well as for sharing workload increases. Given such models, the objective of the algorithm is to maximize the aggregate real-time benefit and the ability to tolerate host failures during the time window of adaptation functions. Since determining the optimal solution is computationally intractable, BEA heuristically computes near-optimal resource allocations in polynomial-time. We show that BEA can achieve almost the same fault-tolerance ability as full replication, and accrue most of real-time benefit that full replication can accrue. In the meanwhile, BEA requires much fewer replicas than full replication, and hence is cost effective.
6241696
A formally verified application-level framework for real-time scheduling on POSIX real-time operating systems
We present a framework, called meta scheduler, for implementing real-time scheduling algorithms. The meta scheduler is a portable middleware layer component designed for implementations over POSIX-compliant operating systems. It accommodates pluggable real-time scheduling algorithms while offering the flexibility of platform independence - the singular underlying OS requirement is the now nearly ubiquitous POSIX compliance. The versatility of pluggable schedulers positions the meta scheduler for deployment in an interoperable heterogeneous real-time environment. We present the design of the meta scheduler and outline its implementation. Furthermore, we present a mechanized correctness verification using the UPPAAL model checker. Prototype implementation of the meta scheduler over QNX Neutrino real-time operating system demonstrates high performance and a small footprint.
14712997
Proactive QoS negotiation in asynchronous real-time distributed systems
We present a fast, proactive, quality of service (QoS) negotiation algorithm called Best Effort Negotiation (or BEN), for asynchronous real-time distributed systems. BEN considers an application model where trans-node application timeliness and fault-tolerance requirements are expressed using benefit functions, and anticipated workload and system failure rates during future time intervals are expressed using adaptation functions and reliability functions, respectively. Furthermore, BEN considers an adaptation model where subtasks of application tasks are replicated at run-time for tolerating failures as well as for sharing workload increases. Given such models, the objective of the algorithm is to maximize the sum of aggregate real-time and fault-tolerance benefits during the time window of adaptation functions. Since determining the optimal solution is computationally intractable, BEN heuristically computer sub-optimal resource allocations in polynomial-time. To determine how well BEN performs, we describe another algorithm called HLC, that is inspired by the well-known Hill Climbing heuristic. We show that HLC is significantly slower than BEN. However, our experimental studies reveal that the performance of BEN, in general, is as good as that of HLC.
14201193
Adaptive time-critical resource management using time/utility functions: past, present, and future
Time/utility function time constraints (or TUFs) and utility accrual (UA) scheduling optimality criteria, constitute, arguably, the most effective and broadest approach for adaptive, dynamic time-critical resource management. A TUF, which is a generalization of the classical deadline constraint, specifies the utility of completing an application activity as an application-or situation-specific function of that activity's completion time. With TUF time constraints, timeliness optimality criteria can be specified in terms of accrued (e.g., summed) activity utilities. This work overviews past and recent advances on adaptive resource management for dynamic time-critical systems using UA algorithms. Emerging challenges and new research directions are also identified.
45203834
Efficiently tolerating failures in asynchronous real-time distributed systems
We present a proactive resource allocation algorithm, called BEA, for fault-tolerant asynchronous real-time distributed systems. BEA considers an application model where trans-node application timeliness requirements are expressed using benefit functions, and anticipated workload during future time intervals are expressed using adaptation functions. Furthermore, BEA considers an adaptation model where subtasks of application tasks are replicated at run-time for tolerating failures as well as for sharing workload increases. Given such models, the objective of the algorithm is to maximize the aggregate real-time benefit and the ability to tolerate host failures during the time window of adaptation functions. Since determining the optimal solution is computationally intractable, BEA heuristically computes suboptimal resource allocations in polynomial-time. We show that BEA can achieve almost the same fault-tolerance ability as full replication, and accrue most of real-time benefit that full replication can accrue. In the meanwhile, BEA requires much fewer replicas than full replication, and hence is cost effective.
6919037
A systems engineering approach for constructing certifiable real-time distributed systems
In this paper, we present a systems engineering methodology for constructing certifiable realtime distributed systems. In the proposed approach, an architectural and algorithmic solution to an application problem is designed by considering the "weakest" models including the weakest asynchronous computational model and multimodal arrival model. Furthermore, timeliness properties are described using Jensen's benefit accrual predicates. Once a system solution is designed, timeliness properties are established by constructing necessary feasibility conditions that are expressed as non-valued predicates. The predicates are quantified and verified to produce the specification of a certified solution. We illustrate the approach by considering a packet transmission problem that desire soft timeliness. We present a certifiable solution to this problem that consists of switched Ethernet, a soft real-time packet scheduling algorithm (that was previously developed), and feasibility conditions.
18829609
Proposal of Novel Histogram Features for Face Detection
This paper presents novel features for face detection in the paradigm of AdaBoost algorithm. Features are multi-dimensional histograms computed from a set of rectangles in the filtered images, and they represent marginal distributions of these rectangles. The filter banks consist of intensity, Laplacian of Gaussian (Difference of Gaussians), and Gabor filters, aiming at capturing spatial and frequency properties of human faces at different scales and different orientations. The best features selected by AdaBoost, pairs of filter and rectangle, can thus be interpreted as boosted marginal distributions of human faces. The result of preliminary experiments demonstrate that the selected features are much more powerful to describe the face pattern than the simple features of Viola and Jones and some variants which can only capture several moments of ONE dimensional histogram in intensity images.
42771841
Passive velocity field control of mechanical manipulators
Two concepts for the task specification and control for mechanical manipulators are advocated: the coding of tasks in terms of velocity fields; and controllers that maintain the passivity relationship between the manipulator and its physical environment. A passive velocity field tracking controller is proposed. The proposed dynamic controller mimics a flywheel: it stores and releases energy to the manipulator, but does not generate any. The controller has the interesting property that it stabilizes any multiple (positive or negative) of the desired velocity field, and exponentially stabilizes the particular multiple which is related to the total kinetic energy of the manipulator+controller.
9618917
Towards A Robust and Real-time Face Detection and Tracking Framework
Traditional research and development in face detection and tracking are mostly focused on either face detection in still images, or face tracking in image streams, without remarkable combination of both. As a result, few impressive face detection and tracking systems can be seen nowadays. The paper contributes to effectively incorporation of two modules, detection module and tracking module, into one integrated and coupled framework. In the detection module we construct AdaBoost detectors for face detection in video stream, which are able to detect multi-view faces and are robust to illumination changes in video stream. The tracking module is based on the improved mean shift tracking, which has advantage of target model adaption. The detection module, triggered every ten frames, is not only responsible for initiating a tracking thread, but also, together with tracking module, contributes to target model update. The system is able to benefit from the strengths of different techniques and overcome their respective limitations. Experiments on real image sequences show that the system is robust and real-time in realistic environment.
1068580
Visual contour tracking based on particle filters
Abstract The Condensation algorithm, developed for visual tracking, is a variant of particle filter. In the sampling stage of Condensation, no use is made of the information from the current frame in the image sequence. As a consequence, the algorithm requires a large number of particles and is computationally expensive. In this paper, a Kalman particle filter (KPF) and an unscented particle filter (UPF) are applied to contour tracking to try to overcome the problem. These algorithms use the Kalman filter or unscented Kalman filter to incorporate information from the current frame. This sampling strategy can effectively steer the set of particles towards regions with high likelihood, and therefore can considerably reduce the number of particles needed for tracking. Performance comparisons show that the KPF is an improvement over Condensation, while the UPF has a much higher computational cost for equal tracking error.
46149042
Data reconciliation for real-time optimization of an industrial coke-oven-gas purification process
Online optimization is more and more used in the chemical industry to run a process near its optimum operating condition by providing real-time computed optimal set-points to the distributed control system. Process measurements are necessary for these applications to determine the actual state of the process and to increase the accuracy of the model with parameter estimation techniques. However, these measurements usually contain random as well as gross errors which have to be identified and eliminated before the measurements are used for online optimization. In this contribution, a data reconciliation approach was integrated into an online optimization framework for the ammonia hydrogen sulfide circulation scrubbing, a common industrial coke-oven-gas purification process. We used a rigorous rate-based model to describe this reactive absorption and desorption process. To increase the accuracy of the model, we estimated several process parameters using a sequential parameter estimation approach. Data reconciliation was performed based on simple component balances to achieve model-consistent data and to identify measurement biases. The model was then validated online on a pilot plant by connecting the estimation package through the process control system. Based on the online measured data, operating cost minimization was carried out and the computed optimal set-points realized real-time. A satisfactory agreement between measured data and optimization was achieved.