Asynchronous Distributed Algorithms in the Theta-Model

It has been taken for granted for many years that fault-tolerant distributed real-time computing problems admit solutions in synchronous computational models only. Synchronous models assume that explicit bounds upon computation step times and transmission delays are a priori known and respected by all correct parts of the system. Today`s leading system implementations, like the time triggered architecture, are hence all built upon the synchronous paradigm. However, ensuring that assumed bounds on computation times and transmission delays are always met is notoriously difficult with many systems, especially those built out of COTS products. The safety properties achieved with such synchronous systems may hence have a poor coverage. It is well-known, however, that safety properties, like "any two correct server replicas always provide consistent response to client requests", can also be guaranteed in asynchronous computational models. Since asynchronous algorithms do not depend upon timing assumptions, they cannot violate safety and liveness properties in case the underlying system`s assumed timing properties are not met, for example, in case of unanticipated overload or denial-of-service attacks. The coverage of such time-free solutions (and thus the probability of correct operation under unanticipated operating conditions) is hence possibly significantly higher than that of a solution involving some timing assumptions. The proposed project 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.

It has been taken for granted for many years that fault-tolerant distributed real-time computing problems admit solutions in synchronous computational models only. Synchronous models assume that explicit bounds upon computation step times and transmission delays are a priori known and respected by all correct parts of the system. Today`s leading system implementations, like the time triggered architecture, are hence all built upon the synchronous paradigm. However, ensuring that assumed bounds on computation times and transmission delays are always met is notoriously difficult with many systems, especially those built out of COTS products. The safety properties achieved with such synchronous systems may hence have a poor coverage. It is well-known, however, that safety properties, like "any two correct server replicas always provide consistent response to client requests", can also be guaranteed in asynchronous computational models. Since asynchronous algorithms do not depend upon timing assumptions, they cannot violate safety and liveness properties in case the underlying system`s assumed timing properties are not met, for example, in case of unanticipated overload or denial-of-service attacks. The coverage of such time-free solutions (and thus the probability of correct operation under unanticipated operating conditions) is hence possibly significantly higher than that of a solution involving some timing assumptions. The proposed project 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.