Leslie Lamport
P. M. Melliar-Smith
Abstract
Algorithms are described for maintaining clock synchrony in a distributed multiprocess system where each process has its own clock. These algorithms work in the presence of arbitrary clock or process failures, including “two-faced clocks” that present different values to different processes. Two of the algorithms require that fewer than one-third of the processes be faulty. A third algorithm works if fewer than half the processes are faulty, but requires digital signatures.
- 1 DOLEV, D.The Byzantine Generals strike again. J. Algor. 3, 1 (1982), 14-30.Google Scholar
- 2 DOLEV, D., AND STRONG, R.Authenticated algorithms for Byzantine Agreement. SIAM. J. 12, 4 (Nov. 1983), 656-666.Google Scholar
- 3 HALPERN, J., SIMONS, B., ANt) STRONG, R.An efficient fault-tolerant algorithm for clock synchronization. IBM Tech. Rep. RJ-4094, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1983.Google Scholar
- 4 LAMPORT, L.The implementation of reliable distributed multiprocess systems. Comput. Netw. 2 (1978),95-114.Google Scholar
- 5 LAMPORT, L.Using time instead of timeout for fault-tolerant distributed systems. ACM Trans. Prog. Lang. Syst., to appear. Google Scholar
- 6 LAMPORT, L., SHOSTAK, R., AND PEASE, M.The Byzantine Generals problem. ACM Trans. Prog. Lang. Syst. 4, 3 (July 1982), 382-401. Google Scholar
- 7 PEASE, M., SHOSTAK, R., AND LAMPORT, L.Reaching agreement in the presence of faults. J. ACM 27, 2 (Apr. 1980), 228-234. Google Scholar
- 8 STRONG, H. R., AND DOLEV, D.Byzantine Agreement. In Intellectual Leverage for the Information Society (Compcon). New York: IEEE Computer Society Press, pp. 77-82.Google Scholar
- 9 DOLEV, D., HALPERN, J. Y., AND STRONG, H. R. On the possibility and impossibility of achieving clock synchronization. In Proceedings of 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., Apr. 30-May 2). ACM, New York, 1984, pp. 504-511. Google Scholar
- 10 WENSL~Y, J., ET AL.SIFT: Design and analysis of a fault-tolerant computer for aircraft control. Proceedings of the jrEEE 66, 10 (Oct. 1978).Google Scholar
Index Terms
- Synchronizing clocks in the presence of faults
Recommendations
A Hybrid Approach for Synchronizing Clocks in Distributed Systems
Cloud Computing – CLOUD 2019AbstractThe art of synchronizing clocks across a wide area network has got a new dimension when it comes to the reality of achieving the demand for high-accuracy synchronization; even for local or small computing systems. Before implementing any clock ...
Synchronizing Hypercube Networks in the Presence of Faults
Synchronizing distributed networks allows nodes to share resources efficiently, run synchronous programs and vote on redundant results in fault tolerant systems. Due to the low connectivity of hypercube networks, neither the fault tolerant hardware ...
Reviews
Robert Joel Hofkin
Virtually all distributed system work assumes that independent local clocks remain in agreement to form a single time base. In fact, the clocks drift and must be resynchronized periodically. Despite its shortcomings, a classic paper by Lamport [1] convinced most researchers that clocks could be synchronized arbitrarily well, and the problem was ignored. The present paper revisits the mechanisms for clock synchronization and presents three algorithms that work despite clock or process failures. The treatment is theoretical and based on Byzantine Generals solutions. It is assumed that communication delays are short and predictable (the paper suggests 2 &mgr;sec.), and that the clocks are reasonably accurate as well (suggested error 1 &mgr;sec.). These assumptions will hold in some, but certainly not all, distributed systems. Of course there is no free lunch: the best clock synchronization comes from frequent updates over predictable links. Analysis is lacking for less predictable, but very common, links such as CSMA.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments