Using atomic broadcast to implement a posteriori agreement for clock synchronization.

Luís Rodrigues, Paulo Veríssimo and António Casimiro From the Proceedings of the 12th Symposium On Reliable Distributed Systems, Oct. 6-8, 1993, Princeton, New Jersey.

Abstract

In a recent paper we presented a new clock synchronization algorithm, dubbed a posteriori agreement, a variant of the convergence non-averaging technique. By exploiting the characteristics of broadcast networks, the effect of message delivery delay variance is largely reduced. In consequence, the precision achieved by the algorithm is drastically improved. Accuracy preservation is near to optimal.

In this paper we present a particular materialization of this algorithm, implemented as a time service of the xAMp group communications system. The algorithm was implemented using some of the primitives offered by xAMp, which simplified the work and stressed its advantages. The paper also presents performance results for this implementation obtained on two different infrastructures. Timings validate the design choices and clearly show that our algorithm is able to provide improved precision without compromising accuracy and reliability.

Also available extended report (gzip postscript), (pdf) .


Luís Rodrigues