Dynamic aspects of modelling distributed computations

Abstract

Diese Dissertation beschäftigt sich mit einer in der Regel vernachlässigten Facette der Modellierung verteilter Berechnungen: der Dynamizität. Die Folgen solcher, nämlich dynamischer, Annahmen werden hierbei anhand der Lösbarkeit des Konsensusproblems untersucht.<br /> Klassischerweise werden die meisten Aspekte eines verteilten Systems als statisch angenommen; beispielsweise, gilt eine Komponente immerfort als fehlerhaft sobald sie sich einmal fehlerhaft verhalten hat. Ein anderer Aspekt für den dieses Dogma gilt, ist die Synchronität: Ab einem Zeitpunkt (oder auch von Beginn an) wird das System als für immer synchron angenommen. Im Gegensatz dazu beschäftigt sich diese Arbeit mit transienten Fehlern und vorübergehender Synchronität.<br /> Der erste Teil der Arbeit stellt ein generelles Basismodell vor, welches in den folgenden Abschnitten in verschiedene Richtungen spezialisiert wird. Anschließend behandelt diese Arbeit die Beziehung zwischen verschiedenen Synchronitätsannahmen, wobei hier der Fokus zunächst nicht auf der Dynamizität liegt sondern auf die Verwandtschaften zwischen Modellen. Diese Verwandtschaften werden anhand von Modellen mit schließlich synchrone Subsystemen untersucht. Dabei zeigt sich, dass Algorithmen für solche Modelle ineinander transformiert werden können, wenn die schließlich synchronen Subsysteme gleich groß sind. Wie sich Dynamizität der Synchronität auf diese Verwandtschaften auswirkt wird anhand der Effizienz dieser Transformationen behandelt.<br /> Der zweite und dritte Teil der Arbeit befasst sich mit dynamischen Fehlern. Zunächst wird für eine bestimmte Klasse von dynamischen Kommunikationsfehlern gezeigt, dass es bei einer gewissen Anzahl solcher Fehler (in Relation zur Gesamtzahl der Prozesse im System) keine Lösung für das Konsensusproblem geben kann. Anschließend wird durch Design und Analyse optimaler Algorithmen gezeigt, dass diese Anzahl eine strenge Grenze darstellt. Im letzten Abschnitt des dritten Teils wird schließlich eine Lösung für das Konsensusproblem entworfen und analysiert, welche in Systemen mit nur vorübergehend verlässlicher und zeitgerechter Kommunikation (dynamische Synchronität) und vorübergehend byzantinischen Prozessen (dynamische Prozessfehler) korrekt funktioniert.<br />

This thesis deals with an aspect of the modelling of distributed computations that is usually neglected in the existing literature: the possibly dynamic behaviour of the underlying system. The implications of employing assumptions that model this dynamic phenomena are investigated by analyzing their effect on the solvability of the consensus problem. Classically all aspects of a distributed system are assumed to be static. For instance, a component that behaves faulty once is considered to be incorrect throughout the whole execution. Another aspect where this dogma is still valid (maybe to a lesser extent) is synchrony:<br />Distributed systems are typically assumed to be synchronous forever (either from the beginning or from some point onwards). Contrasting these assumptions, this thesis is devoted to transient failures and intermittent synchrony.<br /> In the first part of the thesis a generic model is introduced which will be refined in several ways later on. Subsequently, the relations between certain kinds of synchrony assumptions are investigated. In doing so we do not focus on the dynamicity at first, but rather concentrate on the relation between models, which all have eventually synchronous subsystems (what this means exactly differs between the models). By using algorithm transformations, it is shown that all studied models are related which share the same size of their eventually synchronous subsystem. The efficiency of these transformations is then used to reason about the relations between models where synchrony is only intermittent.<br /> The second and third part of this thesis deals primarily with dynamic failures. First, it is shown that for a certain class of communication failures it is impossible to solve consensus if a certain ratio between the number of failures and the number of processes in the system is exceeded. Subsequently, it is shown through the design and analysis of optimal algorithms that this ratio is, in fact, a tight bound. Lastly, we devise an algorithm which is able to solve consensus in systems which alternate between synchronous and asynchronous periods (dynamic synchrony) and allows transient Byzantine faulty processes (dynamic failures).<br />