**RR Number**- 49/2005
**Conference**- Distributed Computing
**Author(s)**- Josef Widder, Ulrich Schmid
**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.
**Bibtex**@Article{WS09:DC, author = {Josef Widder and Ulrich Schmid}, title = {The {T}heta-{M}odel: Achieving Synchrony without Clocks}, journal = {Distributed Computing}, year = {2009}, publisher = {Springer Verlag}, volume = {22}, number = {1}, pages = {29--47}, month = apr }

**Download**- Get paper.pdf - Adobe PDF-format, (331.4629 KB; posted at July 09 2013)