Distributed computing in the presence of bounded asynchrony

Abstract

This thesis investigates various aspects of the [Theta]-Model.<br />The [Theta]-Model is a time free model of distributed systems which assumes that end-to-end delays of the fastest and slowest messages over the network are correlated. This relation is expressed by giving an upper bound [Theta] on the ratio of longest and shortest transmission times of messages which are simultaneously in transit.<br />The model was introduced by Le Lann and Schmid, who showed that the [Theta]-Model is sufficiently strong to solve the fundamental yet not trivial problem of consensus. Their innovative results left room for improvement in the definition of the [Theta]-Model and raised some questions, including the amount of synchrony in the model and related to it what kind of problems have solution in it.<br />The first part of this thesis is dedicated to a refinement of the original definition of the [Theta]-Model. The second major part introduces several algorithms and analyzes their behavior when executed in the [Theta]-Model. The basic algorithm is a clock synchronization algorithm whereupon several other algorithms - e.g.<br />implementation of the perfect failure detector and atomic commitment - are devised. The third part considers booting. The problem of system startup is often neglected in distributed computing theory. This is due to the fact that when real systems are considered, timed semantics are usually employed, which allow several simplifications of the booting problem. Since we consider a time free model, the problem of booting clock synchronization is particularly difficult because classic failure assumption cannot be employed properly in the booting phase.