Conventional schemes of rollback recovery with checkpointing for concurrent processes have overlooked an important problem: contamination of checkpoints as a result of error propagation among the cooperating processes. Error propagation is unavoidable due to imperfect detection mechanisms and random interprocess communications, and it could give rise to contaminated checkpoints which, in turn, result in unsuccessful rollbacks. To counter the problem of error propagation, a damage assessment model is developed to estimate the correctness of saved checkpoints under various circumstances. Using the result of damage assessment, determination of the "optimal" checkpoints for rollback recovery-which minimize the average total recovery overhead-is formulated and solved as a nonlinear integer programming problem. Integration of damage assessment into existing recovery schemes is also discussed.

A new fast switching double processing architecture for pipelined cache-based real-time computer systems is proposed to reduce the CPU stalls due to increased cache misses resulting from frequent task switching in multi-tasking real-time applications. In this architecture, two sets of registers are provided so that two tasks can be executed alternatively on a cycle-by-cycle basis. This architecture helps alleviate the problem of unpredictable cache performance due to frequent context switches in multi-tasking systems. The performance of the double processing is evaluated first through trace driven simulation for various cache configurations. An analytical performance model is then derived to further explain the performance advantage.

In a real-time system, a repetitive task can be scheduled as a periodic task or an adaptive task to meet its timing requirement. For a periodic task, the deadline is always one period interval from the ready time and the current deadline will become the ready time for the next task instance. Whereas for an adaptive task, the deadline is set to one period interval from the completion of the previous task instance and the ready time can be set anywhere before the deadline. Periodic task scheduling has be researched extensively in the past. The authors study the scheduling of adaptive tasks. This study is motivated by the study of resource allocation for a radar system with adaptive sensors, where the resources would be used more efficiently if the sensor tasks are scheduled as adaptive tasks.>

An optimal retry policy in a computer system is usually derived under the unrealistic assumption that fault characteristics are known a priori and remain unchanged throughout the mission lifetime. In such a case, the optimal retry period depends only upon the system's status at the time of fault detection. We propose to remedy this deficiency by formulating the optimal retry problem as a Bayesian decision problem where not only the time of fault detection but also the results of earlier retries are used to estimate the current fault characteristics. Previous knowledge about fault characteristics is represented by the prior distributions of fault-related parameters which are updated whenever new samples are obtained from retry and detection mechanisms. A new fault classification scheme is proposed to assign a temporal fault type (i.e. permanent, intermittent or transient) to each detected fault so that the corresponding fault parameters can be estimated. The estimated fault parameters are then used to derive the optimal retry period that minimizes the mean task completion time. Efficient algorithms are developed to determine the optimal retry period online upon detection of each fault. To evaluate the goodness of the proposed retry policy, it is compared with, and is always found to outperform, a number of fixed retry period policies.>

In order to perform fan-beam reconstruction using projection data collected from a noncircular scanning locus, existing noncircular fan-beam formulas require a derivative of the scanning locus with respect to the rotation angle. A derivative-free noncircular fan-beam reconstruction formula that is based on a geometrical explanation of the circular equispatial fan-beam reconstruction formula is obtained here. A mathematical proof is then provided under the conditions that the source-to-origin distance is symmetric with respect to the origin of the reconstruction coordinate system, is differentiable almost everywhere, and does not change too fast with respect to the rotation angle. The derivative-free noncircular fan-beam reconstruction formula is the same as the circular one, except that the source-to-origin distance is a function of the rotation angle. A typical simulation result for the noncircular fan-beam formula is given.

In the above-titled work by G. T. Gullberg and G. L. Zeng (ibid., vol.11, no.1, p.91-101, 1992), a fan-beam reconstruction formula of a noncircular scanning locus was derived and extended for half-scan cone-beam reconstruction. However, the reconstruction formula is not exact mathematically unless a necessary condition is satisfied. In this correspondence, the commenters derive this necessary condition and provide a geometrical explanation of the condition.

Considering the characteristics of the X-ray microscope system being developed at SUNY at Buffalo and the limitations of available cone-beam reconstruction algorithms, a general cone-beam reconstruction algorithm and several special versions of it are proposed and validated by simulation. The cone-beam algorithm allows various scanning loci, handles reconstruction of rod-shaped specimens which are common in practice, and facilitates near real-time reconstruction by providing the same computational efficiency and parallelism as L.A. Feldkamp et al.'s (1984) algorithm. Although the present cone-beam algorithm is not exact, it consistently gives satisfactory reconstructed images. Furthermore, it has several nice properties if the scanning locus meets some conditions. First, reconstruction within a midplane is exact using a planar scanning locus. Second, the vertical integral of a reconstructed image is equal to that of the actual image. Third, reconstruction is exact if an actual image is independent of rotation axis coordinate z. Also, the general algorithm can uniformize and reduce z-axis artifacts, if a helix-like scanning locus is used.

Scheduling periodic and aperiodic tasks to meet their time constraints has been an important issue in the design of real-time computing systems. Usually, the task scheduling algorithms in such systems must satisfy the deadlines of periodic tasks and provide fast response times for aperiodic tasks. A simple and efficient approach to scheduling real-time tasks is the use of a periodic server in a static preemptive scheduling algorithm. Periodic tasks, including the server, are scheduled at priori to meet their deadlines according to the knowledge of their periods and computation times. The scheduling of aperiodic tasks is then managed by the periodic server during its service time. In this paper, a new scheduling algorithm is proposed. The new algorithm creates a periodic server which will have the highest priority but not necessarily the shortest period. The server is suspended to reduce the overhead if there are no aperiodic tasks waiting, and is activated immediately upon the arrival of the next aperiodic task. After activated, the server performs its duty periodically until all waiting aperiodic tasks are completed. For a set of tasks scheduled by this algorithm, the deadlines of periodic tasks are guaranteed by a deterministic feasibility check, and the mean response time of aperiodic tasks are estimated using a queueing model. Based on the analytical results, we can determine the period and service time of the server producing the minimum mean response time for aperiodic tasks. The analytical results are compared with simulation results to demonstrate the correctness of our model.

According to their temporal behavior, faults in computer systems are classified into permanent, intermittent, and transient faults. Since it is impossible to identify the type of a fault upon its first detection, the common practice is to retry the failed instruction one or more times and then use other fault recovery methods, such as rollback or restart, if the retry is not successful. To determine an “optimal” (in some sense) number of retries, we need to know several fault parameters, which can be estimated only after classifying all the faults detected in the past.

Considering the interplay between different phases of fault tolerance, a new problem of locating a faulty module in a computing system is formulated and solved. First, the probability of each module being faulty, or faulty probability, is calculated using the likelihood principle from the model parameters for fault detection, diagnostics, error propagation, and error detection. Then, based on the faulty probabilities and a given required diagnostic coverage, the order in which modules are to be diagnosed and the maximum time allotted to diagnose each module are determined by minimizing the average total diagnostic time. An example is presented and analyzed to answer the question of whether or not a system should delay the diagnosis upon detection of an error until more errors are detected.>

An error propagation model has been developed for multimodule computing systems in which the main parameters are the distribution functions of error propagation times. A digraph model is used to represent a multimodule computing system, and error propagation in the system is modeled by general distributions of error propagation times between all pairs of modules. Two algorithms are developed to compute systematically and efficiently the distributions of error propagation times. Experiments are also conducted to measure the distributions of error propagation times with the fault-tolerant microprocessor (FTMP). Statistical analysis of experimental data shows that the error propagation times in FTMP do not follow a well-known distribution, thus justifying the use of general distributions in the present model.>

Analytical models for the design and evaluation of checkpointing of real-time tasks are developed. First, the execution of a real-time task is modeled under a common assumption of perfect coverage of on-line detection mechanisms (which is termed a basic model). Then, the model is generalized (to an extended model) to include more realistic cases, i.e., imperfect coverages of on-line detection mechanisms and acceptance tests. Finally, we determine an optimal placement of checkpoints to minimize the mean task execution time while the probability of an unreliable result (or lack of confidence) is kept below a specified level. In the basic model, it is shown that equidistant intercheckpoint intervals are optimal, whereas this is not necessarily true in the extended model. An algorithm for calculating the optimal number of checkpoints and intercheckpoint intervals is presented with some numerical examples for the extended model.