Entwicklung und Analyse eines fehlertoleranten Atomic Broadcast Protokolls
Seit Jahrzehnten gewinnt der Einsatz von sicherheitskritischen verteilten Systemen mit harten Echtzeitanforderungen in vielen Bereichen wie dem Automobilsektor, Industrie- und Flugkontrollsystemen, der Medizin oder im Nuklearbereich, stetig an Wichtigkeit. Erste Lösungen zur Erzielung von Übereinstimmung unter den Komponenten eines verteilen Systems in Gegenwart von Fehlern existieren bereits seit dem Beginn des ersten Einsatzes eines verteilten Echtzeitsystems und werden seitdem für die unterschiedlichsten Einsatzgebiete um neue Ideen und Lösungen erweitert. Diese Dissertation befasst sich mit dem neuen Protokoll Fault Tolerant Atomic Broadcast and Agreement in Bridge Connected Networks (FABAN), welches für Bridge-verbundene Netzwerke konzipiert ist und Übereinstimmung durch unteilbare Rundsprüche realisiert, indem Nachrichten auf f+1 redundanten Pfaden verteilt werden.
Das ursprünglich informell beschriebene Protokoll, insbesondere die Anforderungen an das redundante Routing, wird für die Fehlerannahme f=1 mathematisch formalisiert und bewiesen. Anschließend wird eine algorithmische Lösung zur effizienten Generierung von Routings vorgestellt, formal bewiesen und experimentell verifiziert. Probleme des Protokolls bei der Toleranz von mehr als einem Fehler werden untersucht und als Folge dessen eine abwärtskompatible Erweiterung von FABAN, genannt ExFABAN, für die Toleranz von f>=1 Fehlern entwickelt. Die Erweiterung wird ebenfalls mathematisch analysiert und hinsichtlich der formulierten Anforderungen formal bewiesen. Sowohl im Bezug auf die Anwendung von FABAN als auch auf ExFABAN wird eine ausführliche Evaluation von geeigneten Netzwerktopologien durchgeführt.
Anschließend werden die mathematischen theoretischen Ergebnisse mit Hilfe von Simulationen im Simulationsframework OMNeT++ auf reale, nicht vorhergesehene Probleme untersucht. Dabei werden wenige, das Konzept der Implementierung betreffende Probleme gefunden und Lösungen ausgearbeitet. Zum Abschluss wird eine Demonstration einer Implementierung von FABAN auf realer Hardware, einem Netzwerk aus Ethernet-verbundenen BananaPi R1 Mikrocontrollern, vorgestellt.
Insgesamt wurden mit Fault Tolerant Atomic Broadcast and Agreement in Bridge Connected Networks (FABAN) sowie Extended Fault Tolerant Atomic Broadcast and Agreement in Bridge Connected Networks for Multiple Faults (ExFABAN) praxistaugliche Atomic Broadcast Protokolle für Bridge-verbundene Netzwerke entwickelt, die als Ethernet-Spezialisierung zunehmend im Automatisierungsbereich eingesetzt werden. Die Protokolle lösen dabei das Problem der fehlertoleranten Übereinstimmung von dezentralen Knoten, die gemeinsam eine Automatisierung durchführen, in effizienter Weise hinsichtlich Topologie und Nachrichtenaufwand.
For decades, the use of safety-critical distributed systems with hard real-time requirements has been gaining in importance in many areas such as the automotive sector, industrial and flight control systems, medicine and the nuclear sector. Since the beginning of the usage of safety-critical real-time distributed systems, solutions for achieving agreement among the components of a distributed system in the presence of faults have been developed and the need for new and more efficient solutions targeting a wide variety of areas of application is still increasing. This thesis deals with the new agreement protocol Fault Tolerant Atomic Broadcast and Agreement in Bridge Connected Networks (FABAN), which is designed for bridge-connected networks and aims to achieve agreement with atomic broadcasts by distributing messages along f+1 redundant paths to all receivers, while up to f components maybe faulty at the same time.
The protocol was originally described informally, especially the requirements concerning the message routing, and is reformulated and proven mathematically for the case f=1. In addition, an algorithm for generating message routings is developed, proven and experimentally analysed. FABAN faces some problems tolerating more than one single fault and as a consequence of the studies of the limitations of the original idea behind FABAN, a fully backward compatible extension of the protocol called ExFABAN is developed and mathematically formulated and proven for the general case of tolerating an arbitrary number f>=1 of faults. For FABAN as well as for ExFABAN a detailed evaluation of suitable network topologies has been carried out. Afterwards all theoretical results are verified in simulations implemented in the simulation framework OMNeT++. Theoretically not considered problems have been detected and solutions developed. Finally, a demonstration of an implementation of FABAN on real hardware, a network of Ethernet-connected BananaPi R1 microcontroller, is presented as final contribution of this thesis.
Overall, practical protocols have been developed with Fault Tolerant Atomic Broadcast and Agreement in Bridge Connected Networks (FABAN) and Extended Fault Tolerant Atomic Broadcast and Agreement in Bridge Connected Networks for Multiple Faults (ExFABAN), which are used as an Ethernet specialization in the automation sector. The protocols solve the problem of the fault-tolerant consensus of decentralized nodes, which perform automation tasks together, in an efficient manner with regard to topology and message overhead.