Asynchronous Distributed Algorithms in the Theta-Model

01.11.2004 - 31.05.2008
Research funding project
The project "Distributed Algorithms in the Theta-Model" is devoted to a novel partially synchronous computational model called the Theta-Model, which facilitates the design of time-free distributed algorithms and is hence weaker than the synchronous model. It is based upon the very simple concept of the end-to-end transmission + computational delay between any two correct processes in the execution of round-based distributed algorithms. The Theta-Model just assumes that, at any time, the ratio of maximum vs. minimum delays is bounded by some constant Theta. Backed up by some initial work, we conjecture that this model allows the design of time-free (i.e., asynchronous) algorithms for all interesting problems (fault-tolerant consensus, clock synchronization, atomic commitment etc.) in distributed computing. Moreover, we conjecture that Theta is not necessarily violated when the delay exceeds some assumed maximum bound, such that the Theta-Model achieves higher coverage in real systems than a synchronous model. The Theta-project shall validate our conjectures.

People

Project leader

Sub project leader

Project personnel

Institute

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Research focus

  • Computer Engineering: 100%

Keywords

GermanEnglish
Fehlertolerante EchtzeitsystemeFault-tolerant real-time systems
Verteilte AlgorithmenDistributed Algorithms
Computational Modelscomputational models
Partiell synchrone Systemepartially synchronous systems
Coveragecoverage

Publications