Characterization of eventual Byzantine agreement
Joseph Y. Halpern, Yoram Moses, et al.
PODC 1990
In this paper we analyzed the effect of linear amortization, a technique for implementing continuous clocks, on the precision achieved by a clock synchronization algorithm. We considered this problem in the context of both external and internal clock synchronization. In both cases we showed that, despite popular belief, adding amortization to an existing clock synchronization algorithm need not worsen its precision. In the case of external synchronization, amortization is completely independent of the underlying synchronization algorithm used. For internal synchronization, on the other hand, we had to make two assumptions about the underlying algorithm, namely that the algorithm resynchronizes all clocks within a small real time interval, and that during this interval both old and new clocks stay synchronized. These additional assumptions are not severe restrictions, since all published internal clock synchronization algorithms that guarantee bounds on the maximum deviation between clocks, have these properties.
Joseph Y. Halpern, Yoram Moses, et al.
PODC 1990
Flaviu Cristian
EuroSys 2008
Flaviu Cristian, Bob Dancey, et al.
FTCS 1990
Ray Strong, D. Dolev, et al.
RTSS 1990