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 253 records · Page 14

A Byzantine-Fault Tolerant Self-Stabilizing Protocol for Distributed Clock Synchronization Systems

Embedded distributed systems have become an integral part of safety-critical computing applications, necessitating system designs that incorporate fault tolerant clock synchronization in order to achieve ultra-reliable assurance levels. Many efficient clock synchronization protocols do not, however, address Byzantine failures, and most protocols that do tolerate Byzantine failures do not self-stabilize. Of the Byzantine self-stabilizing clock synchronization algorithms that exist in the literature, they are based on either unjustifiably strong assumptions about initial synchrony of the nodes or on the existence of a common pulse at the nodes. The Byzantine self-stabilizing clock synchronization protocol presented here does not rely on any assumptions about the initial state of the clocks. Furthermore, there is neither a central clock nor an externally generated pulse system. The proposed protocol converges deterministically, is scalable, and self-stabilizes in a short amount of time. The convergence time is linear with respect to the self-stabilization period. Proofs of the correctness of the protocol as well as the results of formal verification efforts are reported.

Malekpour, Mahyar R.↗

NASA Tech Briefs, August 2004

Topics covered include: Data Relay Board with Protocol for High-Speed, Free-Space Optical Communications; Software and Algorithms for Biomedical Image Data Processing and Visualization; Rapid Chemometric Filtering of Spectral Data; Prioritizing Scientific Data for Transmission; Determining Sizes of Particles in a Flow from DPIV Data; Faster Processing for Inverting GPS Occultation Data; FPGA-Based, Self-Checking, Fault-Tolerant Computers; Ultralow-Power Digital Correlator for Microwave Polarimetry; Grounding Headphones for Protection Against ESD; Lightweight Stacks of Direct Methanol Fuel Cells; Highly Efficient Vector-Inversion Pulse Generators; Estimating Basic Preliminary Design Performances of Aerospace Vehicles; Framework for Development of Object-Oriented Software; Analyzing Spacecraft Telecommunication Systems; Collaborative Planning of Robotic Exploration; Tools for Administration of a UNIX-Based Network; Preparing and Analyzing Iced Airfoils; Evaluating Performance of Components; Fuels Containing Methane of Natural Gas in Solution; Direct Electrolytic Deposition of Mats of MnxOy Nanowires; Bubble Eliminator Based on Centrifugal Flow; Inflatable Emergency Atmospheric-Entry Vehicles; Lightweight Deployable Mirrors with Tensegrity Supports; Centrifugal Adsorption Cartridge System; Ultrasonic Apparatus for Pulverizing Brittle Material; Transplanting Retinal Cells using Bucky Paper for Support; Using an Ultrasonic Instrument to Size Extravascular Bubbles; Coronagraphic Notch Filter for Raman Spectroscopy; On-the-Fly Mapping for Calibrating Directional Antennas; Working Fluids for Increasing Capacities of Heat Pipes; Computationally-Efficient Minimum-Time Aircraft Routes in the Presence of Winds; Liquid-Metal-Fed Pulsed Plasma Thrusters; Personal Radiation Protection System; and Attitude Control for a Solar-Sail Spacecraft.

Source record↗

A distributed programming environment for Ada

Despite considerable commercial exploitation of fault tolerance systems, significant and difficult research problems remain in such areas as fault detection and correction. A research project is described which constructs a distributed computing test bed for loosely coupled computers. The project is constructing a tool kit to support research into distributed control algorithms, including a distributed Ada compiler, distributed debugger, test harnesses, and environment monitors. The Ada compiler is being written in Ada and will implement distributed computing at the subsystem level. The design goal is to provide a variety of control mechanics for distributed programming while retaining total transparency at the code level.

Brennan, Peter↗

Highly-efficient quantum Fourier transformations for certain non-Abelian groups

Quantum Fourier transformations are an essential component of many quantum algorithms, from prime factoring to quantum simulation. While the standard Abelian QFrT is well studied, important variants corresponding to non-Abelian groups of interest have seen less development. In particular, fast non-Abelian Fourier transformations are important components for both quantum simulations of field theories as well as approaches to the non-Abelian hidden subgroup problem. In this work, we present fast quantum Fourier transformations for a number of non-Abelian groups of interest for high energy physics, B T , B O , 6 Δ ( 27 ) , Δ ( 54 ) , and Σ ( 36 × 3 ) . For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations. Our work shows that the development of a fast Fourier transformation can substantively reduce simulation costs by an up to three orders of magnitude for the finite groups that we have investigated.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Efficient Routing of Quantum LDPC Codes on Programmable 2D Toric Architectures

Quantum low-density parity-check codes are promising candidates towards scalable fault-tolerant quantum computation. Among these, bivariate bicycle (BB) codes offer superior encoding rates and large code distance compared to surface codes. However, their requirement on long-range stabilizer measurements poses significant challenges for implementation on realistic hardware with limited connectivity, such as superconducting circuit platforms. In this work, we introduce a novel hardware-software co-design that leverages a programmable communication network architecture to address these limitations. Our approach utilizes a 2D toric network of oscillators as a flexible communication fabric linking qubits at each site. Such architecture significantly reduces the number of long-range couplers required from O ( n ) to O (√ n ). Dual-rail qubits, along with native gates including Swap-Wait-Swap gates and beamsplitter SWAPs, ensure that long-range two-qubit gates can be executed with high fidelity and low latency. To further enhance performance, our qubit layout and routing algorithm utilize symmetries of the codes and enable maximum parallelism for long-range two-qubit gates, maintaining a low syndrome extraction cycle duration and scalability over the code length. We perform circuit-level simulation with realistic noise modeling based on experimental hardware parameters, observing an logical error rate per logical qubit per cycle of 3.06% for [[18,4,4]] BB code, 2.6× less than the existing experimental result. These findings provide a practical roadmap and identify key technological advancements needed to achieve low-overhead fault-tolerant quantum computing at scale.

Liu, Kun [Yale Univ., New Haven, CT (United States↗

Quantum-classical embedding via ghost Gutzwiller approximation for enhanced simulations of correlated electron systems

Simulating correlated materials on present-day quantum hardware remains challenging due to limited quantum resources. Quantum embedding methods offer a promising route by reducing computational complexity through the mapping of bulk systems onto effective impurity models, allowing more feasible simulations on pre- and early-fault-tolerant quantum devices. Here, this work develops a quantum-classical embedding framework based on the ghost Gutzwiller approximation to enable quantum-enhanced simulations of ground-state properties and spectral functions of correlated electron systems. Circuit complexity is analyzed using an adaptive variational quantum algorithm on a statevector simulator, applied to the infinite-dimensional Hubbard model with increasing ghost mode numbers from 3 to 5, resulting in circuit depths growing from 16 to 104. Noise effects are examined using a realistic error model, revealing significant impact on the spectral weight of the Hubbard bands. To mitigate these effects, the Iceberg quantum error detection code is employed, achieving up to 40% error reduction in simulations. Finally, the accuracy of the density matrix estimation and the derived spectral function is benchmarked on IBM and Quantinuum quantum hardware, featuring distinct qubit-connectivity and employing multiple levels of error mitigation techniques.

Chen, I-Chi [Ames Laboratory (AMES), Ames, IA (Uni↗

Reliable Transport over SpaceWire for James Webb Space Telescope (JWST) Focal Plane Electronics (FPE) Network

NASA's James Webb Space Telescope (JWST) faces difficult technical and budgetary challenges to overcome before it is scheduled launch in 2010. The Integrated Science Instrument Module (ISIM), shares these challenges. The major challenge addressed in this paper is the data network used to collect, process, compresses and store Infrared data. A total of 114 Mbps of raw information must be collected from 19 sources and delivered to the two redundant data processing units across a twenty meter deployed thermally restricted interface. Further data must be transferred to the solid-state recorder and the spacecraft. The JWST detectors are kept at cryogenic temperatures to obtain the sensitivity necessary to measure faint energy sources. The Focal Plane Electronics (FPE) that sample the detector, generate packets from the samples, and transmit these packets to the processing electronics must dissipate little power in order to help keep the detectors at these cold temperatures. Separating the low powered front-end electronics from the higher-powered processing electronics, and using a simple high-speed protocol to transmit the detector data minimize the power dissipation near the detectors. Low Voltage Differential Signaling (LVDS) drivers were considered an obvious choice for physical layer because of their high speed and low power. The mechanical restriction on the number cables across the thermal interface force the Image packets to be concentrated upon two high-speed links. These links connect the many image packet sources, Focal Plane Electronics (FPE), located near the cryogenic detectors to the processing electronics on the spacecraft structure. From 12 to 10,000 seconds of raw data are processed to make up an image, various algorithms integrate the pixel data Loss of commands to configure the detectors as well as the loss of science data itself may cause inefficiency in the use of the telescope that are unacceptable given the high cost of the observatory. This combination of requirements necessitates a redundant, fault tolerant, high- speed, low mass, low power network with a low Bit error Rate(1E-9- 1E-12). The ISIM systems team performed many studies of the various network architectures that meeting these requirements. The architecture selected uses the Spacewire protocol, with the addition of a new transport and network layer added to implement end-to-end reliable transport. The network and reliable transport mechanism must be implemented in hardware because of the high average information rate and the restriction on the ability of the detectors to buffer data due to power and size restrictions. This network and transport mechanism was designed to be compatible with existing Spacewire links and routers so that existing equipment and designs may be leveraged upon. The transport layer specification is being coordinated with European Space Agency (ESA), Spacewire Working Group and the Consultative Committee for Space Data System (CCSDS) PlK Standard Onboard Interface (SOIF) panel, with the intent of developing a standard for reliable transport for Spacewire. Changes to the protocol presented are likely since negotiations are ongoing with these groups. A block of RTL VHDL that implements a multi-port Spacewire router with an external user interface will be developed and integrated with an existing Spacewire Link design. The external user interface will be the local interface that sources and sinks packets onto and off of the network (Figure 3). The external user interface implements the network and transport layer and handles acknowledgements and re-tries of packets for reliable transport over the network. Because the design is written in RTL, it may be ported to any technology but will initially be targeted to the new Actel Accelerator series (AX) part. Each link will run at 160 Mbps and the power will be about 0.165 Watt per link worst case in the Actel AX.

Rakow, Glenn↗

Redundant asynchronous microprocessor system for fault tolerant flight control and navigation

Unlike their synchronized counterparts, redundant channels in an asynchronous flight system can, under no-fault conditions, exhibit cross-channel data disparities. Sources of these errors are examined in terms of the general, individual functions of the flight control and navigation application in the asynchronous digital environment. The effects of asynchronism on trajectory programmers, dynamic control algorithms and data reconstruction processes are examined in terms of data skews, data latencies, and clock rate uncertainties. An example is presented in which time corrections are applied to reduce the data disparities. Practical limitations of the approach of the example are discussed.

Dunn, W. R.↗

Enhancing quantum utility: Simulating large-scale quantum spin chains on superconducting quantum computers

We present the quantum simulation of the frustrated quantum spin- 1 2 antiferromagnetic Heisenberg spin chain with competing nearest-neighbor ( J 1 ) and next-nearest-neighbor ( J 2 ) exchange interactions in the real superconducting quantum computer with qubits ranging up to 100. In particular, we implement the Hamiltonian with the next-nearest neighbor exchange interaction in conjunction with the nearest-neighbor interaction on IBM's superconducting quantum computer and carry out the time evolution of the spin chain by employing the first-order Trotterization. Furthermore, our implementation of the second-order Trotterization for the isotropic Heisenberg spin chain, involving only nearest-neighbor exchange interaction, enables precise measurement of the expectation values of staggered magnetization observable across a range of up to 100 qubits. Notably, in both cases, our approach results in a constant circuit depth in each Trotter step, independent of the number of qubits. Our demonstration of the accurate measurement of expectation values for the large-scale quantum system using superconducting quantum computers designates the quantum utility of these devices for investigating various properties of many-body quantum systems. This will be a stepping stone to achieving the quantum advantage over classical ones in simulating quantum systems before the fault tolerance quantum era. Published by the American Physical Society 2024

97 MATHEMATICS AND COMPUTING↗

Navigation Doppler Lidar Signal Processing Architecture and Algorithms

A coherent Doppler lidar has been developed to address the need for a high-performance, compact, and cost-effective velocity and altitude sensor onboard landing vehicles. One of the core subsystems within NDL is its signal processing architecture. The primary function of this subsystem is to digitize the analog output of the homodyned signal received from the photo-diode associated with each telescope, process this signal in the frequency domain, and then turn this information into velocity and range measurements. A secondary function of this subsystem is to setup and control the internal components within NDL and to enable the instrument to interface with external systems by receiving commands, sending telemetry, and synchronizing its measurements with external clocks and pulses. This paper will give an overview of the signal processing architecture within NDL. This will include a discussion on its fundamental processing components and the core signal processing algorithms. Command, telemetry and internal component controls will also be discussed as will how the signal processing architecture has also evolved over the years of development. We will discuss provisions for robust operation including Triple-Mode Redundancy (TMR) within NDL’s Field Programmable Gate Array (FPGA) and storage elements, a fault-tolerant boot process, and Error Detection and Correction (EDAC) on the Static Random-Access Memories (SRAMs). Finally, we conclude this paper with how this architecture could continue to evolve.

Doppler Lidar↗

Improved Fermion Hamiltonians for Quantum Simulations

Constructing improved hamiltonians for gauge theories coupled to fermonic matter will be important for improving continuum limit extrapolations of quantum computations. In this talk we will present a formulation for simulating ASQTAD fermions for lattice computation and provide fault tolerant resource costs in terms of primitive group operations. We additionally show that the scaling of energies with respect to the lattice spacing are better than for the unimproved Hamiltonian for toy models.

Quantum Algorithms↗

Multiple Fault Isolation in Redundant Systems

We consider the problem of sequencing tests to isolate multiple faults in redundant (fault-tolerant) systems with minimum expected testing cost (time). It can be shown that single faults and minimal faults, i.e., minimum number of failures with a failure signature different from the union of failure signatures of individual failures, together with their failure signatures, constitute the necessary information for fault diagnosis in redundant systems. In this paper, we develop an algorithm to find all the minimal faults and their failure signatures. Then, we extend the Sure diagnostic strategies [1] of our previous work to diagnose multiple faults in redundant systems. The proposed algorithms and strategies are illustrated using several examples.

Shakeri, M.↗

Quantum error thresholds for gauge-redundant digitizations of lattice field theories

In the quantum simulation of lattice gauge theories, gauge symmetry can be either fixed or encoded as a redundancy of the Hilbert space. While gauge-fixing reduces the number of qubits, keeping the gauge redundancy can provide code space to mitigate and correct quantum errors by checking and restoring Gauss’s law. In this work, we consider the correctable errors for generic finite gauge groups and design the quantum circuits to detect and correct them. We calculate the error thresholds below which the gauge-redundant digitization with Gauss’s law error correction has better fidelity than the gauge-fixed digitization involving only gauge-invariant states. Our results provide guidance for fault-tolerant quantum simulations of lattice gauge theories. Published by the American Physical Society 2024

97 MATHEMATICS AND COMPUTING↗

The Integrated Safety-Critical Advanced Avionics Communication and Control (ISAACC) System Concept: Infrastructure for ISHM

Integrated System Health Management (ISHM) architectures for spacecraft will include hard real-time, critical subsystems and soft real-time monitoring subsystems. Interaction between these subsystems will be necessary and an architecture supporting multiple criticality levels will be required. Demonstration hardware for the Integrated Safety-Critical Advanced Avionics Communication & Control (ISAACC) system has been developed at NASA Marshall Space Flight Center. It is a modular system using a commercially available time-triggered protocol, ?Tp/C, that supports hard real-time distributed control systems independent of the data transmission medium. The protocol is implemented in hardware and provides guaranteed low-latency messaging with inherent fault-tolerance and fault-containment. Interoperability between modules and systems of modules using the TTP/C is guaranteed through definition of messages and the precise message schedule implemented by the master-less Time Division Multiple Access (TDMA) communications protocol. "Plug-and-play" capability for sensors and actuators provides automatically configurable modules supporting sensor recalibration and control algorithm re-tuning without software modification. Modular components of controlled physical system(s) critical to control algorithm tuning, such as pumps or valve components in an engine, can be replaced or upgraded as "plug and play" components without modification to the ISAACC module hardware or software. ISAACC modules can communicate with other vehicle subsystems through time-triggered protocols or other communications protocols implemented over Ethernet, MIL-STD- 1553 and RS-485/422. Other communication bus physical layers and protocols can be included as required. In this way, the ISAACC modules can be part of a system-of-systems in a vehicle with multi-tier subsystems of varying criticality. The goal of the ISAACC architecture development is control and monitoring of safety critical systems of a manned spacecraft. These systems include spacecraft navigation and attitude control, propulsion, automated docking, vehicle health management and life support. ISAACC can integrate local critical subsystem health management with subsystems performing long term health monitoring. The ISAACC system and its relationship to ISHM will be presented.

Gwaltney, David A.↗

A Blueprint for Demonstrating Quantum Supremacy with Superconducting Qubits

Long coherence times and high fidelity control recently achieved in scalable superconducting circuits paved the way for the growing number of experimental studies of many-qubit quantum coherent phenomena in these devices. Albeit full implementation of quantum error correction and fault tolerant quantum computation remains a challenge the near term pre-error correction devices could allow new fundamental experiments despite inevitable accumulation of errors. One such open question foundational for quantum computing is achieving the so called quantum supremacy, an experimental demonstration of a computational task that takes polynomial time on the quantum computer whereas the best classical algorithm would require exponential time and/or resources. It is possible to formulate such a task for a quantum computer consisting of less than a 100 qubits. The computational task we consider is to provide approximate samples from a non-trivial quantum distribution. This is a generalization for the case of superconducting circuits of ideas behind boson sampling protocol for quantum optics introduced by Arkhipov and Aaronson. In this presentation we discuss a proof-of-principle demonstration of such a sampling task on a 9-qubit chain of superconducting gmon qubits developed by Google. We discuss theoretical analysis of the driven evolution of the device resulting in output approximating samples from a uniform distribution in the Hilbert space, a quantum chaotic state. We analyze quantum chaotic characteristics of the output of the circuit and the time required to generate a sufficiently complex quantum distribution. We demonstrate that the classical simulation of the sampling output requires exponential resources by connecting the task of calculating the output amplitudes to the sign problem of the Quantum Monte Carlo method. We also discuss the detailed theoretical modeling required to achieve high fidelity control and calibration of the multi-qubit unitary evolution in the device. We use a novel cross-entropy statistical metric as a figure of merit to verify the output and calibrate the device controls. Finally, we demonstrate the statistics of the wave function amplitudes generated on the 9-gmon chain and verify the quantum chaotic nature of the generated quantum distribution. This verifies the implementation of the quantum supremacy protocol.

Kechedzhi, Kostyantyn↗

Preparing Fermions via Classical Sampling and Linear Combinations of Unitaries

We present an extension of the Evolving density matrices on Qubits (E$ρ$OQ) framework that enables efficient fault-tolerant preparation of fermionic quantum states. The original method circumvents state preparation by stochastic sampling, but faces a sign problem in fermionic systems leading to a large number of circuits necessary. We resolve this by combining classical stochastic sampling with a linear combination of unitaries method that avoids the exponential circuit scaling that plagued naïve implementations. The resulting algorithm requires $\mathcal{O}(M^2)$$R_Z$ rotations for circuit preparation, where $M$ is the number of retained basis states. We validate the method for ground and excited states in the Thirring model, including by computing two-point correlation functions relevant to scattering. In this model for fixed accuracy $\varepsilon$, $M$ is found to scale empirically as $M \propto \frac{1}{mg}\log(1/g)\log(1/m)$.

Gustafson, Erik J. [RIACS, Mtn. View] (ORCID:00000↗

Permutation codes for the state assignment of fault tolerant sequential machines

A new fault-tolerant state assignment method is suggested for synchronous sequential machines. It is assumed that the inputs are fault free and that for no input it is possible to reach all or most of the states, whose number may be fairly large. Error correcting codes for the state assignment are generated by permutations of a chosen linear code. A state assignment algorithm is developed and its computational complexity is estimated. Examples are given.

Chen, M.↗