[ main page ] [ back ]

2009 : Dynamic Aspects of Modeling Distributed Computations

Author(s)
Martin Biely
Abstract
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 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 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).
Bibtex
@phdthesis{Bie09:diss,
  author =      "Martin Biely",
  title =       "Dynamic Aspects of Modeling Distributed Computations",
  address =     "Treitlstr. 3/3/182-1, 1040 Vienna, Austria",
  school =      "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  year =        "2010"
}
Download
Get diss.pdf - Adobe PDF-format, (729.9717 KB; posted at July 09 2013)


[ main page ] [ back ]