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.