Fault-tolerant hardware implementation of a consensus algorithm

Abstract

Diese Master-Arbeit entwickelt ein neues Kommunikationsmodell für digitale elektronische Systeme. Das vorgeschlagene Schema ist vergleichbar mit einem GALS (globally asynchronous locally synchronous) System mit dem Unterschied, dass bei unserer Lösung die Taktquellen eine a-prior bekannte, beschrankte Präzision aufweisen. Diese schwache Synchronität wird ausgenutzt um ein Kommunikationssystem welches (i) konzeptuell frei von Metastabilität ist und (ii) ein vollkommen vorhersagbares zeitliches Verhalten hat zu entwickeln. Deshalb stellt das Kommunikationsschema ein synchrones Verhalten zur Verfügung, welches die Anwendung von Techniken gestattet, die auf synchrone Systeme beschränkt sind. Zusätzlich vermeidet dieses Schema den zentralen Clock als Single Point of Failure. Um die nicht perfekte Synchronisation zwischen den lokalen Clock Signalen (innerhalb der Präzision) zu kompensieren wird auf jeder Kommunikationsverbindung ein FIFO Buffer verwendet.<br />Mittels der Theorie der Verteilten Systeme wird die Korrektheit des Ansatzes formal bewiesen. Dazu werden die Kommunikationsvorgänge als verteilter Algorithmus modelliert. Genauer gesagt wird gezeigt, dass, unter der Voraussetzung dass die Buffergröße über einem gewissen, formal bewiesenen Mindestwert liegt, metastabilitäts- und fehlerfreie Kommunikation möglich ist. Weiters wird eine effiziente Hardware Implementierung vorgestellt und diese zur experimentellen Validierung der theoretischen FIFO Buffer Größe verwendet. Es zeigt sich, dass die bewiesene minimal benötigte Speichergröße eine größte untere Schranke darstellt. Ein Vergleich der Leistungsfähigkeit mit einem traditionellen GALS System zeigt, dass unsere Lösung einen höheren Datendurchsatz hat.<br />Basierend auf dem neuen Kommunikationsmodell wird ein fehlertolerantes elektronisches System entwickelt, welches auch dann in der Lage ist byzantinische Fehler zu tolerieren, wenn die Module nicht replikations-deterministisch sind. Dazu wird zuerst die Verwendbarkeit von TMR Systemen untersucht. Da diese jedoch als nicht einsetzbar eingestuft werden, muss stattdessen auf eine Hardware-Implementierung des bekannten byzantinischen EIG Consensus Algorithmus zurückgegriffen werden.<br />Da der EIG Algorithmus ein lockstep synchroner Algorithmus ist, wird basierend auf dem Kommunikationsmodel ein lockstep synchroneres Rundenmodell implementiert. Weiters wird der EIG Algorithmus so angepasst, dass er effizient in Hardware implementierbar ist. Die Äquivalenz des adaptierten Algorithmus mit dem Original wird gezeigt.<br />Weiters wird die Hardware-Implementierung eines Systems, welches einen byzantinischen Fehler tolerieren kann, beschrieben. Die Leistung und Komplexität der Implementierung werden ebenfalls analysiert.<br />

This thesis develops a new communication model for digital electronic systems. The proposed scheme is comparable to a GALS (globally asynchronous locally synchronous) system with the difference that the clock sources have a bounded, a-priory known precision. This loose synchrony is exploited to establish a communication that (i) is free of metastability by design and (ii) has a fully predictable temporal behavior. As a consequence the communication scheme presents a synchronous behavior, thus allowing to employ techniques that are restricted to synchronous systems, while avoiding the central clock being a single point of failure. To compensate for the imperfect synchronization of the local clocks (within the defined precision), a FIFO buffer memory is used on each communication link. Using the theory of distributed systems the correctness of the approach is formally proved. For this purpose the communication activity is modeled as a distributed algorithm. More specifically it is shown that metastability-free and correct communication is possible, given that the buffer is larger than a certain, formally proved minimum. Furthermore an efficient hardware implementation is given and used to experimentally show that the theoretical derived FIFO buffer size requirement represents a tight lower bound. A performance comparison with a traditional GALS system shows that the performance of our solution is superior.<br />Based on the new communication model, a fault tolerant electronic system, able to tolerate Byzantine faults even in case of non replica deterministic modules, is developed. First the usability of a TMR system in such a setting is analyzed and, as found inadequate, replaced by a hardware implementation of the commonly known Byzantine EIG consensus algorithm.<br />As the EIG algorithm is lockstep synchronous, the lockstep synchronous model is simulated on top of our communication model. The EIG algorithm is adapted such that it can be efficiently implemented in hardware based on the timings established by the lockstep rounds. The equivalence of the adapted algorithm and the original EIG algorithm is shown.<br />Additionally the hardware implementation for a system tolerating a single Byzantine fault is sketched. Performance and complexity of the implementation are analyzed.<br />