[Back]

M. Biely:
"Dynamic Aspects of Modelling Distributed Computations";
Supervisor, Reviewer: U. Schmid, B. Charron-Bost; Institut für Technische Informatik, 2009; oral examination: 2009-11-30.

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: 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
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 dynamicity, but rather
concentrate on the relation between models first, 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, that share the same size of their
eventually synchronous subsystem, are related. The efficiency of these transformations
is finally used to reason about the relations between models where synchrony is only
intermittent.
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).

http://publik.tuwien.ac.at/files/PubDat_184409.pdf