49/2005 : The Theta-Model: Achieving Synchrony without Clocks

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.46 KB; posted at November 12 2008)