Abstract
The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.
- 1 Schwartz, J.T. Relativity in lllustrations. New York U. Press, New York, 1962.Google Scholar
- 2 Taylor, E.F., and Wheeler, J.A. Space-Time Physics, W.H. Freeman, San Francisco, 1966.Google Scholar
- 3 Lamport, L. The implementation of reliable distributed multiprocess systems. To appear in Computer Networks.Google Scholar
- 4 Ellingson, C, and Kulpinski, R.J. Dissemination of system-time. 1EEE Trans. Comm. Com-23, 5 (May 1973), 605-624.Google ScholarCross Ref
Index Terms
- Time, clocks, and the ordering of events in a distributed system
Recommendations
A Hybrid Approach for Synchronizing Clocks in Distributed Systems
Cloud Computing – CLOUD 2019AbstractThe art of synchronizing clocks across a wide area network has got a new dimension when it comes to the reality of achieving the demand for high-accuracy synchronization; even for local or small computing systems. Before implementing any clock ...
Simulating synchronized clocks and common knowledge in distributed systems
Time and knowledge are studied in synchronous and asynchronous distributed systems. A large class of problems that can be solved using logical clocks as if they were perfectly synchronized clocks is formally characterized. For the same class of problems,...
Using integer clocks to verify clock-synchronization protocols
We use the Uppaal model checker for timed automata to verify the Timing-Sync time-synchronization protocol for sensor networks (TPSN), the clock-synchronization algorithm of Lenzen, Locher and Wattenhofer (LLW) for general distributed systems, and the ...
Comments