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

Created from the Publication Database of the Vienna University of Technology.