Solving the labeling problem : a Byzantine fault-tolerant self-stabilizing FPGA prototype based on the FATAL+ protocol

Abstract

Das Thema dieser Masterarbeit liegt im Querschnitt der Gebiete VLSI-Design und fehlertoleranter verteilter Algorithmen. Sie ist einer FPGA Implementierung des bekannten synchronen Phase King Konsensus Algorithmus mittels 1-bit serieller Kommunikation und der Entwicklung einer entsprechenden Testumgebung gewidmet. Die Implementierung wurde darüber hinaus mit einem bereits existierenden Prototyp eines selbst-stabilisierenden, fehlertoleranten verteilten Algorithmus zur Taktgenerierung integriert, um ohne Verlängerung der Stabilisierungszeit 17-bit breite synchronisierte Uhren zur Verfügung stellen zu können. Die Arbeit untersucht auch mögliche Implementierungsalternativen und enthält die Korrektheitsbeweise der verwendeten Algorithmen.<br />

The topic of this thesis lies in the intersection of VLSI design and fault-tolerant distributed algorithms.<br />It is devoted to the development of an FPGA implementation of the well-known synchronous Phase King consensus algorithm using single-bit serial communication and the design of a suitable testbench for verifying its operation. The implementation is finally integrated into an existing prototype and testbench of the self-stabilizing Byzantine fault-tolerant distributed clock generation scheme FATAL+, where it is used to generate 17-bit wide synchronized clocks without increasing the stabilization time of the underlying scheme. The thesis also explores implementation alternatives and provides the correctness proofs of the employed algorithm.