Engineering topics

Miner, Paul S.

Publications and source records attributed to Miner, Paul S..

25 records · Page 2

NASA NTRS1993

Verification of fault-tolerant clock synchronization systems

A critical function in a fault-tolerant computer architecture is the synchronization of the redundant computing elements. The synchronization algorithm must include safeguards to ensure that failed components do not corrupt the behavior of good clocks. Reasoning about fault-tolerant clock synchronization is difficult because of the possibility of subtle interactions involving failed components. Therefore, mechanical proof systems are used to ensure that the verification of the synchronization system is correct. In 1987, Schneider presented a general proof of correctness for several fault-tolerant clock synchronization algorithms. Subsequently, Shankar verified Schneider's proof by using the mechanical proof system EHDM. This proof ensures that any system satisfying its underlying assumptions will provide Byzantine fault-tolerant clock synchronization. The utility of Shankar's mechanization of Schneider's theory for the verification of clock synchronization systems is explored. Some limitations of Shankar's mechanically verified theory were encountered. With minor modifications to the theory, a mechanically checked proof is provided that removes these limitations. The revised theory also allows for proven recovery from transient faults. Use of the revised theory is illustrated with the verification of an abstract design of a clock synchronization system.

Miner, Paul S.↗

NASA NTRS1992

An extension to Schneider's general paradigm for fault-tolerant clock synchronization

In 1987, Schneider presented a general paradigm that provides a single proof of a number of fault tolerant clock synchronization algorithms. His proof was subsequently subjected to the rigor of mechanical verification by Shankar. However, both Schneider and Shankar assumed a condition Shankar refers to as a bounded delay. This condition states that the elapsed time between synchronization events (i.e., the time that the local process applies an adjustment to its logical clock) is bounded. This property is really a result of the algorithm and should not be assumed in a proof of correctness. This paper remedies this by providing a proof of this property in the context of the general paradigm proposed by Schneider. The argument given is a generalization of Welch and Lynch's proof of a related property for their algorithm.

Miner, Paul S.↗

NASA NTRS1992

A verified design of a fault-tolerant clock synchronization circuit: Preliminary investigations

Schneider demonstrates that many fault tolerant clock synchronization algorithms can be represented as refinements of a single proven correct paradigm. Shankar provides mechanical proof that Schneider's schema achieves Byzantine fault tolerant clock synchronization provided that 11 constraints are satisfied. Some of the constraints are assumptions about physical properties of the system and cannot be established formally. Proofs are given that the fault tolerant midpoint convergence function satisfies three of the constraints. A hardware design is presented, implementing the fault tolerant midpoint function, which is shown to satisfy the remaining constraints. The synchronization circuit will recover completely from transient faults provided the maximum fault assumption is not violated. The initialization protocol for the circuit also provides a recovery mechanism from total system failure caused by correlated transient faults.

Miner, Paul S.↗

NASA NTRS1991

Test and evaluation of the generalized gate logic system simulator

The results of the initial testing of the Generalized Gate Level Logic Simulator (GGLOSS) are discussed. The simulator is a special purpose fault simulator designed to assist in the analysis of the effects of random hardware failures on fault tolerant digital computer systems. The testing of the simulator covers two main areas. First, the simulation results are compared with data obtained by monitoring the behavior of hardware. The circuit used for these comparisons is an incomplete microprocessor design based upon the MIL-STD-1750A Instruction Set Architecture. In the second area of testing, current simulation results are compared with experimental data obtained using precursors of the current tool. In each case, a portion of the earlier experiment is confirmed. The new results are then viewed from a different perspective in order to evaluate the usefulness of this simulation strategy.

Miner, Paul S.↗

NASA NTRS1990

A HOL theory for voting

Central to fault-tolerant computing is redundancy management, and common to proofs of fault-tolerance is a maximum fault assumption. Typically a maximum fault assumption is rather restrictive. Usually, this is necessary to avoid assumptions about the behavior of faulty channels. A maximum fault assumption is useful because it allows reasoning about fault tolerance in the presence of arbitrarily malicious fault behavior. However, analysis of the architecture may establish certain scenarios in which the assumption may be weakened. Proofs comparing majority and plurality and proofs of simple reconfiguration strategies are presented in viewgraph form.

Miner, Paul S.↗

NASA NTRS1989

Characterization of the faulted behavior of digital computers and fault tolerant systems

A development status evaluation is presented for efforts conducted at NASA-Langley since 1977, toward the characterization of the latent fault in digital fault-tolerant systems. Attention is given to the practical, high speed, generalized gate-level logic system simulator developed, as well as to the validation methodology used for the simulator, on the basis of faultable software and hardware simulations employing a prototype MIL-STD-1750A processor. After validation, latency tests will be performed.

Bavuso, Salvatore J.↗

NASA NTRS1987

A latent fault Markov model for a highly reliable triplex computer system

A Markov model of a highly reliable triplex system was constructed to evaluate the probability of system failure as a function of the propagation of latent faults. It is found that if the propagation rate of latent faults is extremely high, they do not significantly affect the probability of system failure, while if the propagation rate is extremely low, the survivability of the system is improved. The propagation rate that is most harmful to the survivability of the system is determined as a function of the duration of the flight. A decrease in the probability of system failure due to latency is noted if the probability of any two faults giving the same output is extremely low.

Swern, Frederic L.↗