Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
2007-12-18
2008-11-18
Levitan, Dmitry (Department: 2616)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
Reexamination Certificate
active
07453910
ABSTRACT:
A system and method to synchronize independent local clocks in multi-core processing system are disclosed. A shared counter or a shared memory/file is provided to establish a partial happened-before relationship (e1<e2in the happened-before order if we know that the event e1happened before the event e2) and a synchronizer device is utilized to generate a global time of events in threads or processes. The synchronizer device estimates each clock's start time and approximates elapsed time between events in threads or processes by executing an all-pair shortest-path algorithm.
REFERENCES:
patent: 4816989 (1989-03-01), Finn et al.
patent: 4816990 (1989-03-01), Williams
patent: 5896524 (1999-04-01), Halstead, Jr. et al.
patent: 6246701 (2001-06-01), Slattery
patent: 6574665 (2003-06-01), Khotimsky
patent: 6633835 (2003-10-01), Moran et al.
patent: 6801940 (2004-10-01), Moran et al.
patent: 6807583 (2004-10-01), Hrischuk et al.
patent: 6826752 (2004-11-01), Thornley et al.
patent: 6963747 (2005-11-01), Elliot
patent: 7062762 (2006-06-01), Krishnamurthy et al.
patent: 7177853 (2007-02-01), Ezra et al.
patent: 7246054 (2007-07-01), Szymanski et al.
patent: 2001/0034223 (2001-10-01), Rieser et al.
patent: 2002/0194393 (2002-12-01), Hrischuk et al.
patent: 2004/0117682 (2004-06-01), Xu
patent: 2005/0080924 (2005-04-01), Shang et al.
patent: 2005/0265258 (2005-12-01), Kodialam et al.
patent: 2007/0244571 (2007-10-01), Wilson et al.
patent: 0473405 (1991-08-01), None
patent: 0747803 (1996-11-01), None
patent: WO 2006/055955 (2006-05-01), None
patent: WO 2007/064490 (2007-06-01), None
Arvind, K., “Probabilistic Clock Synchronization in Distributed Systems”, IEEE Transactions on Parallell and Distributed Systems, vol. 5, No. 5, May 1994, pp. 474-487.
Cristian, F., “Probabilistic Internal Clock Synchronization”, Distributed Computing, vol. 3, No. 3, Sep. 1989, pp. 146-158.
Johnson, D.B. et al., “Recovery in Distributed Systems Using Optimistic Message Logging and Checkpointing”, Proceedings 7thAnnual ACM Symposium on Principles of Distributed Computing, 1988, pp. 1-10.
Lamport, L., “Time, Clocks, and the Ordering of Events in a Distributed System”, Communications of the ACM, vol. 21, No. 7, Jul. 1978, pp. 558-565.
Mattern, F., “Virtual Time and Global States of Distributed Systems”, Parallel and Distributed Algorithms, Proceedings of the International Workshop, 1989, pp. 120-131.
Meier, L., “Internal Synchronization of Drift-Constraint Clocks in Ad-Hoc Sensor Networks”, International Symposium on Mobile Ad Hoc Networking & Computing, Proceedings of the 5thACM International Symposium on Mobile Ad Hoc Networking and Computing, 1994, pp. 90-97.
Olson, A., “Probabilistic Clock Synchronization in Large Distributed Systems”, IEEE Transactions on Computers, vol. 43, No. 9, Sep. 1994, pp. 1106-1112.
Ostrovsky, R., “Optimal and Efficient Clock Synchronization Under Drifting Clocks”, Annual ACM Symposium on Principles of Distributed Computing, Proceedings of the 18thAnnual ACM Symposium on Principles of Distributed Computing, pp. 1-17.
Ramanathan, P., “Fault-Tolerant Clock Synchronization in Distributed Systems”, Computer, IEEE Computer Society, vol. 23, No. 10, Oct. 1990, pp. 33-42.
Sichitiu, M. L., “Simple, Accurate Time Synchronization for Wireless Sensor Networks”, Wireless Communications and Networking, IEEE, vol. 2, Mar. 16-20, 2003,pp. 1266-1273.
Farnam Jahanian, et al., “Runtime Monitoring of Timing Constraints in Distributed Real-Time Systems”, Technical Report CSE-TR 212-94, University of Michigan, Apr. 1994, pp. 1-21.
Robert W. Floyd, “Algorithm 97:Shortest Path”, Communications of the ACM, 1962, p. 345, vol. 5, Issue 6, ACM.
David L. Mills, “Network Time Protocol (NTP) General Overview”, Aug. 2, 2004, 22 pages.
David L. Mills, “Network Tlme Protocol Version 4 Reference and Implementation Guide”, Jun. 2006, 90 pages.
David L. Mills, “NTP Architecture, Protocol and Algorithms”, Jul. 22, 2007, 26 pages.
David L. Mills, NTP Clock Discipline Principles, Aug. 24, 2004, 14 pages.
David L. Mills, “NTP Performance Analysis”, Aug. 24, 2004, 19 pages.
David L. Mills, “NTP Procedure Descriptions and Flow Diagrams” Apr. 16, 2005, 43 pages.
Stephen Warshall, “A Theorem on Boolean Matrices”, Journal of the ACM, 1962, p. 11-12, vol. 9, Issue 1, ACM.
Biberstein Marina
Harel Yuval
Heilper Andre
Erez Suzanne
International Business Machines - Corporation
Levitan Dmitry
Scully , Scott, Murphy & Presser, P.C.
LandOfFree
Synchronization of independent clocks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Synchronization of independent clocks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synchronization of independent clocks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4049812