|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
DOLEV, D.The Byzantine Generals strike again. J. Algor. 3, 1 (1982), 14-30.
|
| |
2
|
DOLEV, D., AND STRONG, R.Authenticated algorithms for Byzantine Agreement. SIAM. J. 12, 4 (Nov. 1983), 656-666.
|
| |
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.
|
| |
4
|
LAMPORT, L.The implementation of reliable distributed multiprocess systems. Comput. Netw. 2 (1978),95-114.
|
 |
5
|
|
| |
6
|
|
| |
7
|
|
| |
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.
|
| |
9
|
|
| |
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).
|
CITED BY 86
|
|
|
|
|
|
|
|
Ying Zhao , Wanlei Zhou , Elicia J. Lanham , Shui Yu , Mingjun Lan, Self-adaptive clock synchronization based on clock precision difference, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.181-187, February 01, 2003, Adelaide, Australia
|
|
|
|
|
|
|
|
|
|
|
|
Boaz Barak , Shai Halevi , Amir Herzberg , Dalit Naor, Clock synchronization with faults and recoveries (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.133-142, July 16-19, 2000, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yoram Moses , Ben Bloom, Knowledge, timed precedence and clocks (preliminary report), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.294-303, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
Hagit Attiya , Amir Herzberg , Sergio Rajsbaum, Optimal clock synchronization under different delay assumptions, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.109-120, August 15-18, 1993, Ithaca, New York, United States
|
|
|
|
|
|
|
|
|
Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
|
|
|
Stephen R. Mahaney , Fred B. Schneider, Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.237-249, August 1985, Minaki, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
Danny Dolev , Rüdiger Reischuk , Ray Strong, Observable clock synchronization extended abstract, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.284-293, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. Powell , J. Arlat , L. Beus-Dukic , A. Bondavalli , P. Coppola , A. Fantechi , E. Jenn , C. Rabéjac , A. Wellings, GUARDS: A Generic Upgradable Architecture for Real-Time Dependable Systems, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.580-599, June 1999
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sirio Scipioni , Leonardo Querzoni , Sara Tucci Piergiovanni , Roberto Baldoni, A theoretical evaluation of peer-to-peer internal clock synchronization, Proceedings of the 2nd International Conference on Autonomic Computing and Communication Systems, p.1-8, September 23-25, 2008, Turin, Italy
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
REVIEW
"Robert Joel Hofkin : Reviewer"
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 [
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.4