Fault-tolerant clock synchronization in distributed systems with low topological requirements
Verteilte Echtzeitsysteme sind ein wichtiger Teil verschiedener industrieller Anwendungen wie z.B. sicherheitskritische Automatisierung geworden. Diese Systeme müssen fehlertolerante Protokolle zur Uhrensynchronisation einschließen, um eine ausreichende Zuverlässigkeit zu erreichen. Da Fehlfunktionen von Knoten nicht vollständig vermieden werden können, müssen geeignete Fehlertoleranzverfahren entwickelt werden. Dies schließt die Tolerierung von Byzantinischen Fehlern ein, obwohl anzunehmen ist, dass sie nur selten auftreten. Außerdem unterliegen viele sicherheitskritische Systeme Kostenbeschränkungen in Bezug auf die Anzahl der Knoten und Verbindungen zwischen diesen. Dadurch kommt einigen Eigenschaften eine entscheidende Rolle zu, wie z.B. die effiziente Nutzung der strukturellen Redundanz und der Overhead in Bezug auf die Anzahl der kommunizierten Nachrichten. Die hauptsächliche Besonderheit der fehlertoleranten Uhrensynchronisationsprotokolle, die in dieser Arbeit präsentiert werden, liegt in ihrer Anwendbarkeit in Bridge-verbundenen Punkt-zu-Punkt-Netzwerken (wie Ethernet oder Time-Sensitive Network) mit Ring-Topologien, die nur eine einzige zusätzliche Verbindung benötigen, um zwei disjunkte Pfade zwischen jedem Paar von Bridges bereitzustellen. Trotz dieser sehr geringen strukturellen Redundanz (verglichen mit anderen redundanten Topologien und vollvermaschten Netzen) kann nahezu beliebiges Verhalten von einer fehlerhaften Bridge toleriert werden. Wenn eine begrenzte Reduktion der Synchronisationsgenauigkeit akzeptabel ist, kann sogar das vollständige Byzantinische Fehlermodell abgedeckt werden. Alle fünf präsentierten Protokollen nutzen die beiden redundanten Pfade, um im Uhrzeigersinn und im Gegenuhrzeigersinn Zeitinformation zu senden und zu garantieren, dass über mindestens einen Pfad korrekte Information empfangen wird. Durch spezielle Protokoll-Mechanismen und Entscheidungsfunktionen wird das Problem gelöst, dass im Uhrzeigersinn und im Gegenuhrzeigersinn widersprüchliche Information empfangen werden kann (beispielsweise durch nicht erkennbare Fehlmessung der Verarbeitungsdauer verursacht). Die fehlerfreien Bridges gewinnen stets eine konsistente Sicht, so dass sie ihre Uhren mit hinreichender Konvergenz einstellen können.
Distributed real-time systems have become an important part of different industrial applications such as safety-critical computing. These systems need to integrate fault-tolerant clock synchronization protocols to achieve sufficient reliability. Since malfunctions of nodes cannot be completely avoided, appropriate fault-tolerance mechanisms should be developed. This includes even the tolerance of Byzantine behavior although it is expected to occur rarely. Additionally, many safety-critical systems are subject to cost restrictions with respect to the number of nodes and connections between them. This makes some properties crucial, such as the efficient utilization of structural redundancy and the protocol overhead in terms of the number of communicated messages.
The fundamental feature of the fault-tolerant clock synchronization protocols presented in this work is their usability in point-to-point bridge-connected networks (like Ethernet or Time-Sensitive Network) with ring topologies, which require only a single additional link to achieve two disjoint paths between any pair of bridges. Despite this very low structural redundancy (compared to other redundant topologies and fully-meshed networks) nearly arbitrary behavior of one faulty bridge can be tolerated. If a limited reduction in synchronization precision is acceptable, even the full Byzantine failure model is covered. By all of the five proposed protocols the usage of two disjoint paths for sending clockwise and counterclockwise ensures the reception of correct information via at least one path. Special protocol mechanisms and decision functions solve the problem of contradicting information a bridge receives in clockwise and counterclockwise direction (caused by undetectable wrong measurement of processing delays, for example). In any case the fault-free bridges obtain a consistent view to adjust their clocks with sufficient convergence.