Search

Diese Arbeit analysiert die M��glichkeit die traditionellen, dreifach redundanten Fehlertoleranzmechanismen durch Konsensus-Implementierungen zu ersetzen. Nach einem ��berblick ��ber g��ngige Fehlertoleranzans��tze und einer Er��rterung der Probleme bei der Verwendung von Triple Modular Redundancy und Replikadeterminismus werden das Consensus Problem und die zugrundeliegenden Modelle er��rtert. Anhand der theoretischen Modelle werden verwandte Probleme wie Byzantine Agreement und Reliable Broadcast vorgestellt und eine Reduktion von Agreement mit TMR und Replikadeterminismus zu Consensus pr��sentiert. Eine theoretische Analyse bekannter Konsensusprotokolle, n��mlich des Exponential Information Gathering, des Phase King und des Phase Queen Algorithmus, sowie deren f��r Hardware-Implementierung modifizierte Versionen, wird durchgef��hrt. Die theoretischen Eigenschaften der Protokolle werden im Detail analysiert und mit zus��tzlichen Daten aus Fehlerinjektions-Simulationen erweitert. Diese Zusatzinformationen erm��glichen Einblicke in das Verhalten der Protokolle, wenn diese au��erhalb der festgelegten Spezifikation ausgef��hrt werden. Das Phase King Protokoll und das Exponential Information Gathering Protokoll werden auf einem Field Programmable Gate Array (FPGA) Netzwerk implementiert. Da ein einzelner Clock Tree, wie er in synchronen Systemen g��ngig ist, ein gewaltiges Fehlerpotenzial aufweist, wurde zugunsten einer Implementierung mittels verteiltem System entschieden. Dies wurde durch Zuhilfenahme des Distributed Algorithms for Robust Tick-Synchronization (DARTS) Protokolls und eines parametrisierbaren Kommunikatonsbuffers, der metastabilit��tsfreie Kommunikation in dieser Konfiguration erlaubt, erreicht. Die Implementierung dieser zwei Protokolle zeigt, dass verteilte Algorithmen daf��r geeignet sind, ein byzantinisch fehlertolerantes Hardwaresystem zu entwickeln., This thesis explores the possibility of using a consensus algorithm to replace the traditional, triple modular redundancy scheme for fault tolerance. We start with the presentation of state of the art fault tolerance mechanisms and discuss the advantages and drawbacks of TMR systems. To be able to compare these mechanisms to our approach, we outline the basics of distributed algorithms and discuss different consensus algorithms found in literature. Based on this theoretical background a reduction of TMR and replica determinism to consensus has been created. A theoretical evaluation of the well known Exponential Information Gathering protocol, the Phase King protocol and the Phase Queen protocol as well as modifications of these protocols to implement them directly in hardware is given. The theoretical results are analyzed in detail and augmented by results from fault injection experiments performed using a software simulator. As the simulator was specifically tailored to incorporate the properties of the target platform, we were able to evaluate their fitness for direct hardware implementation solely based on the simulation results. As the fault injection experiments were designed to violate the fault hypothesis in some cases, the degradation properties of the algorithms could also be analyzed. The Phase King and the Exponential Information Gathering protocol were implemented on a Field Programmable Gate Array (FPGA) network. To circumvent the single shared clock tree in synchronous systems which introduces a single point of failure we decided to implement the system based on a mesochronous clocking system, namely the Distributed Algorithms for Robust Tick-Synchronization (DARTS) protocol and a fully parametrizable communication buffer supporting metastability free communication in this setting. The implementation of these two illustrate that Byzantine fault tolerance using distributed algorithms is achievable in VLSI circuits.