Abstract
We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith [1985]. Realistic aspects of the problem of synchronizing clocks in the presence of faults are considered. One aspect is that clock synchronization is an on-going task, thus the assumption that some of the processors never fail is too optimistic. To cope with this reality, we suggest self-stabilizing protocols that stabilize in any (long enough) period in which less than a third of the processors are faulty. Another aspect is that the clock value of each processor is bounded. A single transient fault may cause the clock to reach the upper bound. Therefore, we suggest a bounded clock that wraps around when appropriate.We present two randomized self-stabilizing protocols for synchronizing bounded clocks in the presence of Byzantine processor failures. The first protocol assumes that processors have a common pulse, while the second protocol does not. A new type of distributed counter based on the Chinese remainder theorem is used as part of the first protocol.
- Arora, A., Dolev, S., and Gouda, M. 1991. Maintaining digital clocks in step. Parall. Proc. Lett. 1, 1, 11--18.Google Scholar
- Daliot, A., Dolev, D., and Parnas, H. 2002. Self-stabilizing pulse synchronization inspired by biological pacemaker. In Proceedings of the 6th International Symposium on Self-Stabilizing Systems. Lecture Notes in Computer Science, Vol. 2704. Springer-Verlag, New York, 32--48. Google Scholar
- Dijkstra, E. W. 1974. Self stabilizing systems in spite of distributed control. Commun. ACM 17, 643--644. Google Scholar
- Dolev, D., Halpern, J. Y., and Strong, H. R. 1986. On the possibility and impossibility of achieving clock synchronization. J. Comput. Syst. Sci. 32, 2, 230--250. Google Scholar
- Dolev, S., Israeli, A., and Moran, S. 1991. Uniform dynamic self stabilizing leader election. In Proceedings of the 5th International Workshop on Distributed Algorithms. 167--180. Google Scholar
- Dolev, S., Israeli, A., and Moran, S. 1995. Analyzing expected time by scheduler-luck games. IEEE Trans. Softw. Eng. 21, 5 (May). Google Scholar
- Dolev, D., Lynch, N. A., Pinter, S. S., Stark, E. W., and Weihl, W. E. 1986. Reaching approximate agreement in the presence of faults. In J. ACM 33, 499--516. Google Scholar
- Dolev, S. and Welch, J. L. 1993. Wait-free clock synchronization. In Proceedings of the 12th ACM Symposium on Principles of Distributed Computing. ACM, New York, 97--108. Also appeared in Algorithmica 18, 1997, 486--511. Google Scholar
- Cristian, F. 1989. Probabilistic clock synchronization. Distrib. Comput. 3, 146--158.Google Scholar
- Gopal, A. S. and Perry, K. J. 1993. Unifying self-stabilization and fault-tolerance. In Proceedings of the 12th ACM Symposium on Principles of Distributed Computing. ACM, New York, 195--206. Google Scholar
- Halpern, J. Simons, B., Strong, R., and Dolev, D. 1984. Fault-tolerant clock synchronization. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing. ACM, New York, 89--102. Google Scholar
- Knuth, D. E. 1981. The Art of Computer Programming, Vol. 2, 2nd ed., Addison-Wesley, Reading, Mass. Google Scholar
- Lamport, L. and Melliar-Smith, P. M. 1985. Synchronizing clocks in the presence of faults. J. ACM 32, 1, 1--36. Google Scholar
- Lamport, L., Shostak, R., and Pease, M. 1982. The Byzantine generals problem. ACM Trans. Prog. Lang. Syst. 4, 3 (July), 382--401. Google Scholar
- Lundelius, J., and Lynch, N. 1984. An upper and lower bound for clock synchronization. Info. Cont. 62, 190--204.Google Scholar
- Mahaney, S., and Schneider, F.1985. Inexact agreement: Accuracy, precision and graceful degradation. In Proceedings of the 4th ACM Symposium on Principles of Distributed Computing. ACM, New York, 237--249. Google Scholar
- Ramanathan, P., Shin, K. G., and Butler, R. W. 1990. Fault-tolerant clock synchronization in distributed systems. IEEE Comput. (Oct), 33--42. Google Scholar
- Srikanth, T. K. and Toueg, S. 1987. Optimal clock synchronization. J. ACM 34, 3, 626--645. Google Scholar
- Szabo, S., and Tanaka, R. I. 1967. Residue Arithmetic and its Applications to Computer Technology, McGraw-Hill, New York.Google Scholar
- Welch, J. L., and Lynch, N. 1988. A new fault-tolerant algorithm for clock synchronization. Info. Comput. 77, 1, 1--36. Google Scholar
- Wensley, J. H., Lamport, L., Goldberg, J., Green, M. W., Levitt, K. N., Melliar-Smith, P. M., Shostak, R. E., and Weinstock, C. B.1978. SIFT: Design and analysis of fault-tolerant computer for aircraft control. Proc. IEEE 66, 10, 1240--1255.Google Scholar
Index Terms
- Self-stabilizing clock synchronization in the presence of Byzantine faults
Recommendations
Fast self-stabilizing byzantine tolerant digital clock synchronization
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computingConsider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient faults that alter their memory in an arbitrary fashion. Within the context of this model, we are ...
A Byzantine-fault tolerant self-stabilizing protocol for distributed clock synchronization systems
SSS'06: Proceedings of the 8th international conference on Stabilization, safety, and security of distributed systemsEmbedded distributed systems have become an integral part of safety-critical computing applications, necessitating system designs that incorporate fault tolerant clock synchronization in order to achieve ultra-reliable assurance levels. Many efficient ...
Dynamic fault-tolerant clock synchronization
This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. Assuming a fault-tolerant authentication protocol, the ...
Comments