Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Fault Tolerant Algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1984

Fault-tolerant system considerations for a redundant strapdown inertial measurement unit

The development and evaluation of a fault-tolerant system for the Redundant Strapdown Inertial Measurement Unit (RSDIMU) being developed and evaluated by the NASA Langley Research Center was continued. The RSDIMU consists of four two-degree-of-freedom gyros and accelerometers mounted on the faces of a semi-octahedron which can be separated into two halves for damage protection. Compensated and uncompensated fault-tolerant system failure decision algorithms were compared. An algorithm to compensate for sensor noise effects in the fault-tolerant system thresholds was evaluated via simulation. The effects of sensor location and magnitude of the vehicle structural modes on system performance were assessed. A threshold generation algorithm, which incorporates noise compensation and filtered parity equation residuals for structural mode compensation, was evaluated. The effects of the fault-tolerant system on navigational accuracy were also considered. A sensor error parametric study was performed in an attempt to improve the soft failure detection capability without obtaining false alarms. Also examined was an FDI system strategy based on the pairwise comparison of sensor measurements. This strategy has the specific advantage of, in many instances, successfully detecting and isolating up to two simultaneously occurring failures.

Motyka, P.↗
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 NTRS1990

The design and proof of correctness of a fault-tolerant circuit

The flowing achievements are presented in view graph form: (1) a formal statement of interactive consistency conditions in the Boyer-Moore logic; (2) a formal statement of the oral messages (OM) algorithm in the Boyer-Moore logic; (3) a mechanically checked proof that OM satisfies the interactive consistency conditions; (4) a mechanically checked proof of the optimality result--no algorithm can tolerate fewer faults than OM yet still achieve interactive consistency; (5) the use of OM in a functional specification for a fault-tolerant device; (6) a formal description of the design of the device; (7) a mechanically checked proof that the device design satisfies the specification; and (8) an implementation of the design in programmable logic arrays.

Bevier, William R.↗
NASA NTRS1988

A survey of provably correct fault-tolerant clock synchronization techniques

Six provably correct fault-tolerant clock synchronization algorithms are examined. These algorithms are all presented in the same notation to permit easier comprehension and comparison. The advantages and disadvantages of the different techniques are examined and issues related to the implementation of these algorithms are discussed. The paper argues for the use of such algorithms in life-critical applications.

Butler, Ricky W.↗
NASA NTRS1988

Fault-tolerant clock synchronization techniques for avionics systems

This paper examines six provably correct fault-tolerant clock synchronization algorithms. These algorithms are all presented in the same notation to enable easier comprehension and comparison. The advantages and disadvantages of the different techniques are examined and issues related to the implementation of these algorithms are discussed. The paper argues for the use of such algorithms in life-critical applications.

Butler, Ricky W.↗
NASA NTRS1990

Fault-tolerant clock synchronization in distributed systems

Existing fault-tolerant clock synchronization algorithms are compared and contrasted. These include the following: software synchronization algorithms, such as convergence-averaging, convergence-nonaveraging, and consistency algorithms, as well as probabilistic synchronization; hardware synchronization algorithms; and hybrid synchronization. The worst-case clock skews guaranteed by representative algorithms are compared, along with other important aspects such as time, message, and cost overhead imposed by the algorithms. More recent developments such as hardware-assisted software synchronization and algorithms for synchronizing large, partially connected distributed systems are especially emphasized.

Ramanathan, Parameswaran↗
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 NTRS1994

Current research activities at the NASA-sponsored Illinois Computing Laboratory of Aerospace Systems and Software

The Illinois Computing Laboratory of Aerospace Systems and Software (ICLASS) was established to: (1) pursue research in the areas of aerospace computing systems, software and applications of critical importance to NASA, and (2) to develop and maintain close contacts between researchers at ICLASS and at various NASA centers to stimulate interaction and cooperation, and facilitate technology transfer. Current ICLASS activities are in the areas of parallel architectures and algorithms, reliable and fault tolerant computing, real time systems, distributed systems, software engineering and artificial intelligence.

Smith, Kathryn A.↗
NASA NTRS2018

A Fault-Tolerant Clock Synchronization and Geometry Determination Protocol

A fault-tolerant distributed protocol (algorithm) is presented that achieves optimum timing precision (clock synchronization) among the nodes and, simultaneously, determines the network's geometry (shape) - locations and distances of the nodes relative to each other - in a wireless distributed system. This protocol is based on the assumption of initial coarse synchrony of nodes' local clocks. The proposed solution assumes no prior knowledge of the nodes' locations, the distances between the nodes, or network's geometry, but assumes an ordered geometry where nodes have unique identifiers. This protocol accommodates large variations in the communication latencies among the nodes; thus, it applies equally to both wireless and wired networks.

Malekpour, Mahyar R.↗
NASA NTRS1986

Reconfiguration algorithms for tree architectures using sub-tree oriented fault tolerance

An approach to reconfiguration in tree architectures has been developed in which redundant processors are allocated at the leaves. The scheme is called sub-tree oriented fault tolerances (SOFT) and is capable of tolerating both link failures as well as multiple processor failures. In this paper, the SOFT scheme is examined from the perspective of reconfigurability. Specific algorithms are presented for reconfiguration.

Lowrie, M. B.↗
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 NTRS1984

A validation methodology for fault-tolerant clock synchronization

A validation method for the synchronization subsystem of a fault-tolerant computer system is presented. The high reliability requirement of flight crucial systems precludes the use of most traditional validation methods. The method presented utilizes formal design proof to uncover design and coding errors and experimentation to validate the assumptions of the design proof. The experimental method is described and illustrated by validating an experimental implementation of the Software Implemented Fault Tolerance (SIFT) clock synchronization algorithm. The design proof of the algorithm defines the maximum skew between any two nonfaulty clocks in the system in terms of theoretical upper bounds on certain system parameters. The quantile to which each parameter must be estimated is determined by a combinatorial analysis of the system reliability. The parameters are measured by direct and indirect means, and upper bounds are estimated. A nonparametric method based on an asymptotic property of the tail of a distribution is used to estimate the upper bound of a critical system parameter. Although the proof process is very costly, it is extremely valuable when validating the crucial synchronization subsystem.

Johnson, S. C.↗
NASA NTRS1990

Machine-checked proofs of the design and implementation of a fault-tolerant circuit

A formally verified implementation of the 'oral messages' algorithm of Pease, Shostak, and Lamport is described. An abstract implementation of the algorithm is verified to achieve interactive consistency in the presence of faults. This abstract characterization is then mapped down to a hardware level implementation which inherits the fault-tolerant characteristics of the abstract version. All steps in the proof were checked with the Boyer-Moore theorem prover. A significant results is the demonstration of a fault-tolerant device that is formally specified and whose implementation is proved correct with respect to this specification. A significant simplifying assumption is that the redundant processors behave synchronously. A mechanically checked proof that the oral messages algorithm is 'optimal' in the sense that no algorithm which achieves agreement via similar message passing can tolerate a larger proportion of faulty processor is also described.

Bevier, William R.↗
NASA NTRS2007

Hypothetical Scenario Generator for Fault-Tolerant Diagnosis

The Hypothetical Scenario Generator for Fault-tolerant Diagnostics (HSG) is an algorithm being developed in conjunction with other components of artificial- intelligence systems for automated diagnosis and prognosis of faults in spacecraft, aircraft, and other complex engineering systems. By incorporating prognostic capabilities along with advanced diagnostic capabilities, these developments hold promise to increase the safety and affordability of the affected engineering systems by making it possible to obtain timely and accurate information on the statuses of the systems and predicting impending failures well in advance. The HSG is a specific instance of a hypothetical- scenario generator that implements an innovative approach for performing diagnostic reasoning when data are missing. The special purpose served by the HSG is to (1) look for all possible ways in which the present state of the engineering system can be mapped with respect to a given model and (2) generate a prioritized set of future possible states and the scenarios of which they are parts.

James, Mark↗
NASA NTRS1984

Communications protocols for a fault tolerant, integrated local area network for Space Station applications

The evolutionary growth of the Space Station and the diverse activities onboard are expected to require a hierarchy of integrated,local area networks capable of supporting data, voice and video communications. In addition, fault tolerant network operation is necessary to protect communications between critical systems attached to the net and to relieve the valuable human resources onboard Space Station of day-to-day data system repair tasks. An experimental, local area network is being developed which will serve as a testbed for investigating candidate algorithms and technologies for a fault tolerant, integrated network. The establishment of a set of rules or protocols which govern communications on the net is essential to obtain orderly and reliable operation. A hierarchy of protocols for the experimental network is presented and procedures for data and control communications are described.

Meredith, B. D.↗
NASA NTRS1994

Design and Implementation of a Distributed Version of the NASA Engine Performance Program

Distributed NEPP is a new version of the NASA Engine Performance Program that runs in parallel on a collection of Unix workstations connected through a network. The program is fault-tolerant, efficient, and shows significant speed-up in a multi-user, heterogeneous environment. This report describes the issues involved in designing distributed NEPP, the algorithms the program uses, and the performance distributed NEPP achieves. It develops an analytical model to predict and measure the performance of the simple distribution, multiple distribution, and fault-tolerant distribution algorithms that distributed NEPP incorporates. Finally, the appendices explain how to use distributed NEPP and document the organization of the program's source code.

Cours, Jeffrey T.↗