J. Widder, U. Schmid:

"The Theta-Model: achieving synchrony without clocks";

Distributed Computing,22(2009), 1; 29 - 47.

We present a novel partially synchronous system model, which augments the asynchronous model by a (possibly unknown) bound Theta on the ratio of longest and shortest end-to-end delays of messages simultaneously in transit. An upper bound on those delays need not exist, however, and even Theta may hold only after some unknown global stabilization time. Theta-algorithms are fully message-driven and do not have access to bounded drift local clocks, which makes them particularly suitable for VLSI Systems-on-Chip, for example. In this model, we provide a simulation of (eventually achieved) lock-step rounds, which even works in the presence of Byzantine failures. It follows that most problems in distributed computing have a solution in our model: Using the basic consensus algorithm for partially synchronous systems by Dwork, Lynch and Stockmeyer (1988), for example, Byzantine consensus can be solved. We also introduce a timing transformation technique that facilitates simple correctness proofs and performance analyses of $UR$-algorithms, and provide a detailed relation of the Theta-Model to other partially synchronous system models.

Computing Models, Fault-tolerant distribiuted algorithms, Partially synchronous systems, Clocks and time

http://dx.doi.org/10.1007/s00446-009-0080-x

Created from the Publication Database of the Vienna University of Technology.