Title: Distributed computing in the presence of bounded asynchrony
Language: English
Authors: Widder, Josef
Qualification level: Doctoral
Advisor: Jazayeri, Mehdi
Assisting Advisor: Schmid, Ulrich
Issue Date: 2004
Number of Pages: 104
Qualification level: Doctoral
This thesis investigates various aspects of the [Theta]-Model.
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.
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.
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.
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.
Keywords: Verteilter Algorithmus; Verteiltes System; Echtzeitsystem; Asynchronbetrieb
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-13246
Library ID: AC04223172
Organisation: E182 - Institut für Technische Informatik (Echtzeitsysteme, VLSI-Design) 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

checked on Mar 30, 2021


checked on Mar 30, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.