Byzantine fault quantifying clock synchronization

Details Byzantine fault quantifying clock synchronization Byzantine fault quantifying clock synchronization

2003-10-23

2008-11-18

Dalencourt, Yves (Department: 2157)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

C713S500000, C713S501000, C713S502000, C709S230000, C709S248000

Reexamination Certificate

active

07454521

ABSTRACT:
The clocks of remote computing devices are synchronized within a range of certainty through the determination of an upper bound and a lower bound around a reference time. A message from a computing device is propagated up a network tree of devices to a device having a reference time, which encodes the reference time and returns the message down the tree. Each receiving device can determine that the reference time could not have occurred before their transmission of the message, nor could it have occurred after their receipt of the return message. Cryptographic hashes can be used to guard against malicious computing devices. Alternate paths and scheduling of messages can be used to provide a narrower spread between the upper and lower bounds, and clock drift can be accounted for by increasing the spread over time.

REFERENCES:
patent: 6097811 (2000-08-01), Micali
Mills, David L. “Internet Time Synchronization: the Network Time Protocol”, IEEE Trans. Communications 39, 10 (Oct. 1991). pp. 1482-1493.
Adya, Atul, et al,FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment; Appears in 5thSymposium on Operating Systems Design and Implementation (OSDI 2002), 'Boston, MA, Dec. 2002, pp. 1-14.
Lamport, Leslie, et al.;Byzantine Clock Synchronization; ACM, 1984; pp. 68-74.
Lamport, Leslie, et al.;The Byzantine Generals Problem; ACM Transactions on Programming Languages and Systems, vol. 4, No. 3, Jul. 1982, pp. 382-401.
De Prisco, Roberto, et al.;Revisiting the Paxos Algorithm; MIT Laboratory for computer Science, Cambridge, MA.
Schneider, Fred B.;Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial; ACM Computing Surveys, vol. 22, No. 4, Dec. 1990.
Haber, Stuart, et al.;How to Time-Stamp a Digital Document; Journal of Cryptology, vol. 3, No. 2, 1991, pp. 99-111.
Lamport, Leslie;Using Time Instead of Timeout for Fault-Tolerant Distributed Systems; ACM Transactions on Programming Languages and Systems, vol. 6, No. 2, Apr. 1984, 254-280.
Mills, David L.;Internet Time Synchronization: the Network Time Protocol; IEEE Trans. Communications 39, 10 (Oct. 1991), pp. 1482-1493.
Dwork, Cynthia, et al.;Consensus in the Presence of Partial Synchrony; Journal of the Association for Computing Machinery, vol. 35, No. 2, Apr. 1988, pp. 288-323.
Castro, Miguel, et al.;Practical Byzantine Fault Tolerance; Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, Feb. 1999, pp. 1-14.
Castro, Miguel, et al.;Proactive Recovery in a Byzantine-Fault-Tolerant System; Laboratory for Computer Science, Massachusetts Institute of Technology.
Merkle, Ralph C.,Protocols for Public Key Cryptosystems; ELXSi International, Sunnyvale, CA, pp. 122-134.
De Prisco, Roberto, et al.;Revisiting the PAXOS Algorighm; Theoretical Computer Science 243 (2000) pp. 35-91.
Howard, John H., et al.;Scale and Performance in a Distributed File System; ACM Transactions on Computer Systems, vol. 6, No. 1, Feb. 1988, pp. 51-81.
Lamport, Leslie;The Part-Time Parliament; ACM Transactions on Computer Systems 16, 2 (May 1998), pp. 133-169.
Lamport, Leslie;Time, Clocks, and the Ordering of Events in a Distributed Systems; Communications of the ACM, vol. 21, No. 7, Jul. 1978, pp. 558-565.
Schneider, Fred B.;Understanding Protocols for Byzantine Clock Synchronization; Department of Computer Science, Cornell University; Aug. 1987, pp. 1-35.

Affiliated with

Also associated with

Rating

Byzantine fault quantifying clock synchronization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Byzantine fault quantifying clock synchronization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Byzantine fault quantifying clock synchronization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4047855