The Theta-Model: achieving synchrony without clocks

作     者：Widder, Josef Schmid, Ulrich 

作者机构：Vienna Univ Technol Embedded Comp Syst Grp E182 2 A-1040 Vienna Austria Ecole Polytech Lab Informat LIX F-91128 Palaiseau France 

出 版 物：《DISTRIBUTED COMPUTING》 (分布式计算)

年 卷 期：2009年第22卷第1期

页      面：29-47页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：FWF [P17757-N04] FIT-IT 

主　　题：Computing models Fault-tolerant distributed algorithms Partially synchronous systems Clocks and time 

摘      要：We present a novel partially synchronous system model, which augments the asynchronous model by a (possibly unknown) bound I similar to 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 I similar to may hold only after some unknown global stabilization time. I similar to-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 et al. (J ACM 35(2):288-323, 1988), for example, Byzantine consensus can be solved. We also introduce a timing transformation technique that facilitates simple correctness proofs and performance analyses of I similar to-algorithms, and provide a detailed relation of the I similar to-Model to other partially synchronous system models.