Time, Clocks, and the Ordering of Events in a Distributed System

Leslie Lamport, 1978, Communications of the ACM

About this paperTiếng Việt日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

English
中文

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.

Key Words and Phrases: distributed systems, computer networks, clock synchronization, multiprocess systems

CR Categories: 4.32, 5.29

分布式系统中事件的时间、时钟与排序

Leslie Lamport Massachusetts Computer Associates, Inc.

本文考察了分布式系统中一个事件发生在另一个事件之前的概念，并证明它定义了事件的偏序。给出了一个用于同步逻辑时钟系统的分布式算法，该系统可用于对事件进行全序排序。利用这种全序排序，本文说明了一种解决同步问题的方法。随后，该算法被专门化用于同步物理时钟，并推导出时钟可能产生的最大不同步界限。

关键词和短语：分布式系统，计算机网络，时钟同步，多进程系统

CR 分类：4.32，5.29

Introduction

This section is missing here.

Conclusion

This section is missing here.

Proof of the Theorem

This section is missing here.

References

  1. Schwartz, J.T. Relativity in Illustrations. New York U. Press, New York, 1962.
  2. Taylor, E.F., and Wheeler, J.A. Space-Time Physics, W.H. Freeman, San Francisco, 1966.
  3. Lamport, L. The implementation of reliable distributed multiprocess systems. To appear in Computer Networks.
  4. Ellingson, C., and Kulpinski, R.J. Dissemination of system-time. IEEE Trans. Comm. Com-23, 5 (May 1973), 605–624. Programming Languages J. J. Horning Editor Shallow Binding in Lisp 1.5 Henry G. Baker, Jr. Massachusetts Institute of Technology Shallow binding is a scheme which allows the value of a variable to be accessed in a bounded amount of computation. An elegant model for shallow binding in Lisp 1.5 is presented in which context-switching is an environment tree transformation called rerooting. Rerooting is completely general and reversible, and is optional in the sense that a Lisp 1.5 interpreter will operate correctly whether or not rerooting is invoked on every context change. Since rerooting leaves assoc [v, a] invariant, for all variables v and all environments a, the programmer can have access to a rerooting primitive, shallow[], which gives him dynamic control over whether accesses are shallow or deep, and which affects only the speed of execution of a program, not its semantics. In addition, multiple processes can be active in the same environment structure, so long as rerooting is an indivisible operation. Finally, the concept of rerooting is shown to combine the concept of shallow binding in Lisp with Dijkstra’s display for Algol and hence is a general model for shallow binding. Key Words and Phrases: Lisp 1.5, environment trees, FUNARG’s, shallow binding, deep binding, multiprogramming, Algol display CR Categories: 4.13, 4.22, 4.32 General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM’s copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduction. This research was supported by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Office of Naval Research under contract number N00014-75-C-0522. Author’s present address: Computer Science Department, University of Rochester, Rochester, NY 14627. © 1978 ACM 0001-0782/78/0700-0565 \$00.75 Communications of the ACM July 1978 Volume 21 Number 7

Read off the page by a vision model reading the page images using gpt-5.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 中文 by gpt-5, against glossary version 6. Translated from the English.