Startup and recovery of fault-tolerant time-triggered communication

Abstract

Diese Dissertation beschäftigt sich mit dem Problem der initialen Synchronisation der lokalen Uhren der Kommunikations-Teilnehmer in einem verteilten System. Diese Synchronisation soll eine möglichst genaue Einigung auf den momentanen Punkt der Echtzeit erzielen. Algorithmen die dieses Problem lösen nennt man Startup Algorithmen. Obwohl es verschiedene Wege gibt einen Startup Algorithmus zu konstruieren, haben diese Algorithmen ein gemeinsames Muster: Nach dem Einschalten eines Kommunikations-Teilnehmers muss dieser eruieren, ob es bereits eine Einigung von einer ausreichend großen Anzahl von Teilnehmern bezüglich des aktuellen Zeitpunktes gibt.<br />Wenn eine solche Einigung bereits existiert, muss der Teilnehmer den (Zeit-)Wert dieser Einigung übernehmen, wir sagen, der Teilnehmer muss integrieren. Gibt es eine solche Einigung noch nicht, müssen die Teilnehmer zu einer Einigung kommen.<br />Dieser Prozess wird coldstart genannt. In dieser Dissertation behandeln wir das Startup Problem generell und präsentieren zwei konkrete Startup Algorithmen. Des Weiteren zeigen wir, wie die shared resource, die uns als Kommunikations-Infrastruktur dient, gegen einen beliebig fehlerhaften Teilnehmer geschützt werden kann, und wie ein Startup Algorithmus im Falle eines Synchronisationsverlustes für die Re-Synchronisierung genutzt werden kann.<br />

This thesis addresses the problem of initial synchronizing the local clocks of the participants in a distributed system such that they closely agree on the current point in real-time.<br />Algorithms that solve this problem are known as startup algorithms.<br />Although there are several ways to construct a startup algorithm, they show a common pattern: after power-on, a participant has first to determine if there already exists an agreement of a sufficient set of participants on the current point in real-time. If so, the participant has to join this set, we say the participant has to integrate. If such a set does not exist, the participants have to establish such an agreement. This process is called the coldstart. In this thesis we discuss the startup problem in general and introduce two particular startup algorithms. Furthermore, we show how to protect the shared communication resource against the arbitrary failure of one of its participants, and how a startup algorithm can be used for recovery once the synchronization has been lost.