Distributed Construction of a Fault-Tolerant Wireless Communication Topology for Networked Embedded Systems oder "Implementing the Thallner-Algorithm"
Heinrich Moser · reposiTUm (TU Wien) · 2005
This master's thesis presents a proven-correct implementation of a distributed topology construction algorithm based upon the Thallner topology construction method for creating a minimal ∆-node connected fault-tolerant overlay graph.The algorithm works in asynchronous fault-tolerant distributed systems augmented with failure detectors.A detailed proof shows that given a perfect propose module and a period of network stability, the unique minimal overlay graph is built.This thesis also contains a solvability analysis examining how the algorithm can be implemented in the presence of simple crash failures, in the crash-recovery model and in the presence of lossy links. 1 Zusammenfassung Diese Magisterarbeit präsentiert eine bewiesenermaßen korrekte Implementierung eines verteilten Topologiekonstruktionsalgorithmus basierend auf der Thallner-Methode zur Topologiekonstruktion, mit der ein minimaler ∆-knotenverbundener fehlertoleranter Überlagerungsgraph erzeugt werden kann.Der Algorithmus funktioniert in asynchronen fehlertoleranten verteilten System mit Fehlerdetektoren.Ein detaillierter Beweis zeigt, dass, falls ein perfektes Propose Module zur Verfügung steht und das Netzwerk stabil genug bleibt, der minimale Überlagerungsgraph erzeugt wird.Diese Magisterarbeit enthält weiters eine Lösbarkeitsanalyse, die untersucht, wie der Algorithmus bei einfachen Crash-Fehlern, im Crash-Recovery Modell und bei Nachrichtenverlust implementiert werden kann.