T. K. Srikanth
Abstract
We present a simple, efficient, and unified solution to the problems of synchronizing, initializing, and integrating clocks for systems with different types of failures: crash, omission, and arbitrary failures with and without message authentication. This is the first known solution that achieves optimal accuracy—the accuracy of synchronized clocks (with respect to real time) is as good as that specified for the underlying hardware clocks. The solution is also optimal with respect to the number of faulty processes that can be tolerated to achieve this accuracy.
- 1 BECK, M., SRIKANTH, T. K., AND TOUEG, S. Implementation issues in clock synchronization. In Proceedings of the Asilomar Workshop on Fault Tolerant Distributed Computing. Springer-Verlag, New York. To be published. Google Scholar
- 2 DIFFIE, W., AND HELLMAN, i. New directions in cryptography. IEEE Trans. Inf. Theory IT-22 (1976), 644-654.Google Scholar
- 3 DOLEV, D., HALPERN, J. Y., AND STRONG, R. On the possibility and impossibility of achieving clock synchronization. In Proceedings of the 16th Annual ACM STOC (Washington D.C., Apr.). ACM, New York, 1984, pp. 504-511. (Also to appear in J. Comput. Syst. Sci.) Google Scholar
- 4 DRUMMOND, R. Impact of communication networks on fault-tolerant distributed computing. Ph.D. dissertation, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., 1986. Google Scholar
- 5 FISCHER, M., LYNCH, N., AND MERRITT, M. Easy impossibility proofs for distributed consensus problems. In Proceedings of the 4th Symposium on the Principles of Distributed Computing (Minaki, Canada, Aug.). ACM, New York, 1985, pp. 59-70. Google Scholar
- 6 HADZILACOS, V. Byzantine agreement under restricted types of failures (not telling the truth is different from telling lies). Tech. Rep. 19-83, Aiken Computation Laboratory, Harvard Univ., Cambridge, Mass., June I983.Google Scholar
- 7 HALPERN, J. Y., SIMONS, B., STRONG, R., AND DOLEV, D. Fault-tolerant clock synchronization. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, Canada, Aug.). ACM, New York, 1984, pp. 89-102. Google Scholar
- 8 LAMPORT, L., AND FISCHER, M. Byzantine generals and transaction commit protocols. Opus 62, SRI International, Menlo Park, Calif., Apr. 1982.Google Scholar
- 9 LAMPORT, L., AND MELLIAR-SMITH, P.M. Synchronizing clocks in the presence of faults. J. ACM 32, 1 (Jan. 1985), 52-78. Google Scholar
- 10 LUNDELIUS, J., AND LYNCH, N. A new fault-tolerant algorithm for clock synchronization. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, Canada, Aug.). ACM, New York, 1984, pp. 75-88. Google Scholar
- 11 MAHANEY, S. R., AND SCHNEIDER, F. B. Inexact agreement: Accuracy, precision and graceful degradation. In Proceedings of the 4th Symposium on the Principles of Distributed Computing (Minaki, Canada, Aug.). ACM, New York, 1985, pp. 237-249. Google Scholar
- 12 MARZULLO, K. Maintaining the time in a distributed system. An example of a loosely-coupled distributed service. Ph.D. dissertation, Dept. of Electrical Engineering, Stanford Univ., Stanford, Calif., 1984. Google Scholar
- 13 PERRY, K. J., AND TOUEG, S. Distributed agreement in the presence of processor and communication faults. IEEE Trans. Sofiw. Eng. SE-12, 3 (Mar. 1986), 477-482. Google Scholar
- 14 SRIKANTH, T. K., AND TOUEG, S. Simulating authenticated broadcasts to derive simple faulttolerant algorithms. Tech. Rep. 84-623, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., July 1984. (Also to appear in Distributed Computing, Springer-Verlag, New York.)Google Scholar
Index Terms
- Optimal clock synchronization
Recommendations
Probabilistic clock synchronization
A probabilistic method is proposed for reading remote clocks in distributed systems subject to unbounded random communication delays. The method can achieve clock synchronization precisions superior to those attainable by previously published clock ...
Fault-tolerant external clock synchronization
ICDCS '95: Proceedings of the 15th International Conference on Distributed Computing SystemsAbstract: We address the problem of how to integrate fault-tolerant internal and external clock synchronization. We propose a new algorithm which provides both external and internal clock synchronization for as long as no more than F reference time ...
Reviews
Steven K. Andrianoff
The behavior of distributed systems in the presence of faults has been the subject of much recent research. One area of research is enabling processes to reach agreement as to time. The problem is to provide processes with logical clocks that agree within prescribed bounds, are accurate with respect to real time, and are based on physical clocks for which the bound on the drift rate from real time is known. An additional constraint is that these synchronous clocks are to be maintained in the presence of faulty processes, where a faulty process can exhibit arbitrary behavior. The authors of this paper make an important contribution to the solution of the problem by presenting an optimal algorithm for maintaining synchronous clocks in the presence of faults. The algorithm is optimal in the sense that the logical clocks are as accurate with respect to real time as the underlying physical clocks are. The basic algorithm requires a system with message authentication and yields optimal accuracy provided fewer than half the processes are faulty. The authors modify the basic algorithm by replacing the requirement of a signed communication with one of a broadcast primitive, at the price of tolerating a smaller proportion of faulty processes. They show how the algorithm may be modified further to provide for the initialization of a system of synchronous clocks, for the integration of a process into such a system, and for the maintenance of continuous clocks. This paper has been organized in such a way that it is easy to follow. Detailed proofs of the agreement, accuracy, and optimality results are provided. The treatment of the basic problem and its variations is comprehensive. The authors have placed their results into the context of other published results. As with ther algorithms for distributed services, I would be interested in the performance of the algorithm on an actual system.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments