[Back]


Publications in Scientific Journals:

J. Widder, U. Schmid:
"The Theta-Model: achieving synchrony without clocks";
Distributed Computing, 22 (2009), 1; 29 - 47.



English abstract:
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.

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


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/s00446-009-0080-x


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