Self-stabilizing Byzantine Fault-Tolerant Distributed Algorithms for Integrated Circuits

This project proposes to address robustness issues in very-large scale integrated (VLSI) circuits by means of self- stabilizing Byzantine fault-tolerant distributed algorithms. It aims at the development of the foundations of a suitable framework for correctness proofs and performance analyses for such algorithms, and its application to some representative problems in VLSI circuits. Besides permanent failures due to e.g. manufacturing defects and electrical wear-out, transient faults caused e.g. by ionizing particles, cross-talk and temporarily out-of-spec operating conditions are a major source of concern for the dependability of modern VLSI circuits, in particular, in critical applications domains like aerospace. In sharp contrast to classic fault-tolerance techniques like triple- modular redundancy, self-stabilizing algorithms can recover even from unbounded transient faults, and Byzantine- fault-tolerant self-stabilizing algorithms even allow this to happen in the presence of permanent faults. VLSI circuits put unique challenges on Byzantine fault-tolerant self-stabilizing distributed algorithms, which have not been addressed by existing solutions at all. Besides the fact that millions of simple gates that continuously compute their outputs based on (past) inputs do not match the classic distributed state machine abstraction employed in distributed algorithms, VLSI circuits provide only very simple basic computation and communication features. As a consequence, neither existing distributed algorithms nor existing modeling and analysis frameworks can be carried over without substantial modification. Nevertheless, the Byzantine fault-tolerant self-stabilizing clock generation approach for VLSI circuits developed recently by the authors (in collaboration with Danny Dolev/Hebrew University and Christoph Lenzen/Weizmann Institute) revealed that it is principally feasible to do so. The goal of SIC is to develop the foundations of a framework for the rigorous modeling and analysis of Byzantine fault-tolerant self-stabilizing distributed algorithms for VLSI circuits. The work to be performed in SIC involves solving fundamental research questions, in particular, sound and reasonably complete mathematical descriptions of the stabilization process and digital models for metastability generation and propagation, which cannot be solely addressed by engineering solutions in the self-stabilizing context. This work is complemented by devising Byzantine fault-tolerant self-stabilizing solutions for some representative problems in VLSI circuits, like distributed clock generation and reliable broadcast. Using the envisioned modeling and analysis framework, correctness proofs and performance analyses of these algorithms under adequate Byzantine failure models will be provided. The practical implementability of our algorithms will finally be demonstrated by means of simulation and FPGA prototype implementations, which also facilitate some experimental evaluation.

The SIC project addressed algorithmic ways to improve robustness in circuits. Motivation. There is a large body of work on how to decrease probabilities of such faults on circuit-level, e.g., by choice of material and cell design, and on software-level. However, signicantly less was known about algorithmic techniques on circuit-level. Approach. Interestingly, VLSI circuits can be viewed as distributed systems at several levels of abstraction: gates that communicate via binary signals, up to blocks in a network on chip (NoC). The idea of the SIC project was to use techniques from distributed computing to improve robustness of VLSI circuits. Typically, however, processes are highly restricted in communication primitives and computational power in comparison to the processes that are classically studied in software inspired distributed systems. A focus of the SIC project was on self-stabilizing algorithms: a system solves a problem in a self-stabilizing way if, starting from an arbitrarily corrupted state, it eventually solves the problem. Self-stabilizing algorithms are of great interest for missions where state corruption cannot easily be removed by maintenance or manual reset; e.g., in space missions. Achievements. We tried to tackle the above problems from dierent directions and obtained the following results: (i) We proposed distributed computing models that allow for a formal analysis of algorithms, proving their correctness and performance bounds. Specically we designed a fault-tolerant self-stabilizing distributed clock generation algorithm, designed for implementation at gate-level, and proved it correct. (ii) We pointed out problems in previously existing binary-valued circuit delay models. In follow-up works we proposed new delay models that do not suer from these problems. (iii) Metastability is an inevitable third state any bi-stable device, like a ip-op, may be trapped in for an unbounded time. Devices that are metastable can have adverse eects on their successory circuit if they are read while being metastable. The classical workaround is to wait for metastability to resolve with sucient probability before reading. We demonstrated that waiting is not necessary and how to compute with a metastable state. We also studied ways to measure and characterize metastability. (iv) We combined the above techniques to come up with several robust on-chip services: robust distributed clock generation, clock distribution, clock frequency adaptation in presence of voltage droops, communication infrastructure on a chip, pausable clocks, etc. (v) We studied higher-level algorithms that solve consensus-like problems. The focus was on dynamic networks where the network topology may continuously change.