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

Leslie Lamport, 1978, Communications of the ACM

About this paper中文日本語

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
Tiếng Việt

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

Thời gian, Đồng hồ, và Thứ tự của các Sự kiện trong một Hệ thống Phân tán

Leslie Lamport Massachusetts Computer Associates, Inc.

Khái niệm về việc một sự kiện xảy ra trước một sự kiện khác trong một hệ thống phân tán được xem xét, và được chỉ ra rằng nó xác định một thứ tự từng phần của các sự kiện. Một thuật toán phân tán được đưa ra để đồng bộ hóa một hệ thống các đồng hồ logic, có thể được sử dụng để sắp xếp hoàn toàn các sự kiện. Việc sử dụng thứ tự toàn phần được minh họa bằng một phương pháp giải quyết các vấn đề đồng bộ hóa. Sau đó, thuật toán được chuyên biệt hóa để đồng bộ hóa các đồng hồ vật lý, và một cận được suy ra về mức độ mất đồng bộ mà các đồng hồ có thể đạt tới.

Các từ khóa và cụm từ: hệ thống phân tán, mạng máy tính, đồng bộ hóa đồng hồ, hệ thống đa tiến trình

Các phân loại 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 Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.