Reliability modeling and the mathematical equations involved are discussed for general computer systems organized to be fault tolerant. This paper summarizes the work done over the last four years on mathematical reliability modeling by the authors.

Programmed algorithms for test generation and test evaluation are described. The D-notation is introduced and a test generator (DALG) for combinational logic is presented. The sequential case is then examined. "Real life" constraints related to LSI testing are discussed. Two heuristic test generators satisfying these constraints are introduced. The iterative test generator (ITG) generates tests by transforming the given sequential circuit into an iterative combinational circuit. The macroblock test generator (MTG) uses the same approach but makes use of complex primitives (latches, triggers, etc.) to represent the circuit to be tested. Both the ITG and the MTG are not always guaranteed to generate good tests for each examined failure, and are used in connection with a test evaluator (simulator). Basic features of this evaluator are discussed.

Recovery in a fault-tolerant computer means the continuation of system operation with data integrity after an error occurs. This paper delineates two parallel concepts embodied in the hardware and software functions required for recovery; detection, diagnosis, and reconfiguration for hardware, data integrity, checkpointing, and restart for the software. The hardware relies on the recovery variable set, checking circuits, and diagnostics, and the software relies on the recovery information set, audit, and reconstruct routines, to characterize the system state and assist in recovery when required. Of particular utility is a handware unit, the recovery control unit, which serves as an interface between error detection and software recovery programs in the supervisor and provides dynamic interactive recovery.

Abstract—A computer-oriented algorithm for synthesizing combinational logic circuits from a collection of functionally packaged circuits is developed. The algorithm uses a hierarchy of "goals" in an iterative decision process in a manner similar to that employed by theorem proving and gamne playing programs. With each iteration a set of "tasks" finds the circuit package which satisfies the highest level goal while meeting circuit constraints.

Functionally packaged logic can only be effectively utilized if the totality of switching functions that each package is capable of providing is recognized. Theorems concerning, and algorithms operating on, multiple output switching functions (possibly with don't care conditions) in cubical array notation are presented that 1) detect partial symmetry and redundancy sets of input varibles, 2) determine the function generated by a package with some of its inputs tied to logical 1 or 0 or tied together, and 3) rapidly show equivalence between two functions using symmetry information. While manual execution of the algorithms is possible, they are computer oriented. Results from actual computer experimentation show their efficiency.

Two algorithms are presented: one, DALG-II, computes a test to detect a failure in acyclic logic circuits; the other, TEST-DETECT, ascertains all failures detected by a given test. Both are based upon the utilization of a ``calculus of D-cubes'' that provides the means for effectively performing the necessary computations for very large logic circuits. Strategies for combining the two algorithms into an efficient diagnostic test generation procedure are given. APL specifications of the algorithms are given in an Appendix.

Because transistor NOR gates allow only a liitmed number of inputs, NOR equations must be factored before they can be implemented. An easily programmed algorithm is developed which rapidly generates a subset of factors, selects optimum factors, and indicates a realization for the factored equation based on the relation A ↓ B ↓ C ↓ D = [(A ↓ B) ↓] ↓ C ↓ D. A method for preventing excessive fan-out is also presented.