More Web Proxy on the site http://driver.im/

research-article

Logical Time: Capturing Causality in Distributed Systems

Authors:

Mukesh SinghalAuthors Info & Claims

Computer, Volume 29, Issue 2

Pages 49 - 56

https://doi.org/10.1109/2.485846

Published: 01 February 1996 Publication History

Abstract

A distributed computation consists of a set of processes that cooperate and compete to achieve a common goal. These processes do not share a common global memory and communicately solely by passing messages over a communication network. The communication delay is finite but unpredictable. A process's actions are modeled as three types of events: internal, message send, and message receive. An internal event affects only the process at which it occurs, and the events at a process are linearly ordered by their order of occurrence. Send and receive events signify the flow of information between processes and establish causal dependency from the sender process to the receiver process. Consequently, the execution of a distributed application results in a set of distributed events produced by the process. The causal precedence relation induces a partial order on the events of a distributed computation. Causality among events, more formally the causal precedence relation, is a powerful concept for reasoning, analyzing, and drawing inferences about a distributed computation. Knowledge of the causal precedence relation between processes helps programmers, designers, and the system itself solve a variety of problems in distributed computing. The notion of time is basic to capturing the causality between events. Distributed systems have no built-in physical time and can only approximate it. However, in a distributed computation, both the progress and the interaction between processes occur in spurts. Consequently, logical clocks can be used to accurately capture the causality relation between events. This article presents a general framework of a system of logical clocks in distributed systems and discusses three methods--scalar, vector, and matrix--for implementing logical time in these systems.

References

[1]

D.L. Mills, "On the Accuracy and Stability of Clocks Synchronized by Network Time Protocol in the Internet System," ACM Computer Comm. Rev., Vol. 20, No. 1, Jan. 1990, pp. 65-75.

Digital Library

[2]

L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Comm. ACM, Vol. 21, No. 7, JULY 1978, pp. 558-564.

Digital Library

[3]

C. Fidge, "Logical Time in Distributed Computing Systems," Computer, Vol. 24, No. 8, Aug. 1991, pp. 28-33.

Digital Library

[4]

F. Mattern, "Virtual Time and Global States of Distributed Systems," Proc. Parallel and Distributed Algorithms Conf., North-Holland, Amsterdam, 1988, pp. 215-226.

[5]

F. Schmuck, The Use of Efficient Broadcast in Asynchronous Distributed Systems, doctoral dissertation, Tech. Report TR88-928, Dept. Computer Science, Cornell Univ., Ithaca, New York, 1988, 124 pp.

Digital Library

[6]

B. Charron-Bost, "Concerning the Size of Logical Clocks in Distributed Systems," Information Processing Letters, Vol. 39, JULY 1991, pp. 11-16.

Digital Library

[7]

M.J. Fischer and A. Michael, "Sacrificing Serializability to Attain High Availability of Data in an Unreliable Network," Proc. ACM Symp. Principles Database Systems, ACM Press, New York, 1982, pp. 70-75.

Digital Library

[8]

G.T.J. Wuu and A.J. Bernstein, "Efficient Solutions to the Replicated Log and Dictionary Problems," Proc. 3rd ACM Symp. Principles Distributed Computing, (PODC), ACM Press, New York, 1984, pp. 233-242.

Digital Library

[9]

S.K. Sarin and L. Lynch, "Discarding Obsolete Information in a Replicated Data Base System," IEEE Trans. Software Eng., Vol. SE, No. 13. 1, Jan. 1987, pp. 39-46.

Digital Library

[10]

M. Singhal and A. Kshemkalyani, "An Efficient Implementation of Vector Clocks," Information Processing Letters, Vol. 43, Aug. 1992, pp. 47-52.

Digital Library

[11]

J. Fowler and W. Zwaenepoel, "Causal Distributed Breakpoints," Proc. 10th Int'l Conf. Distributed Computing Systems, 1990, pp. 134-141.

[12]

C. Jard and G-C. Jourdan, "Dependency Tracking and Filtering in Distributed Computations," in Brief Announcements ACM Symp. Principles Distributed Computing, ACM Press, New York, 1994; also Tech. Report No. 851, IRISA, Beaulieu, France, 1994.

Digital Library

[13]

D.S. Parker, et al., "Detection of Mutual Inconsistency in Distributed Systems," IEEE Trans. Software Eng., Vol. SE-9, No. 3, MAY 1983, pp. 240-246.

Digital Library

[14]

B. Liskov and R. Ladin, "Highly Available Distributed Services and Fault-Tolerant Distributed Garbage Collection," Proc. 5th ACM Symp. Principles Distributed Computing, ACM Press, New York, 1986, pp. 29-39.

Digital Library

[15]

R.E. Strom and S. Yemini, "Optimistic Recovery in Distributed Systems," ACM Trans. Computer Systems, Vol. 3, No. 3, Aug. 1985, pp. 204-226.

Digital Library

[16]

M. Raynal, "A Distributed Algorithm to Prevent Mutual Drift Between Logical Clocks," Information Processing Letters, Vol. 24, 1987, pp. 199-202.

Digital Library

[17]

M. Singhal, "A Heuristically-Aided Mutual Exclusion Algorithm for Distributed Systems," IEEE Trans. Computers, Vol. 38, No. 5, MAY 1989, pp. 651-662.

Digital Library

[18]

B. Awerbuch, "Complexity of Network Synchronization," J. ACM, Vol. 32, No. 4, 1985, pp. 804-823.

Digital Library

[19]

M. Raynal and J.M. Helary, Synchronization and Control of Distributed Systems and Programs, John Wiley & Sons, New York, 1990, 124 pp.

Digital Library

[20]

J. Misra, "Distributed Discrete Event Simulation," ACM Computing Surveys, Vol. 18, No. 1, 1986, pp. 39-65.

Digital Library

[21]

R. Righter and J.C. Walrand, "Distributed Simulation of Discrete Event Systems," Proc. IEEE, Jan. 1988, pp. 99-113.

[22]

D. Jefferson, "Virtual Time," ACM Trans. Programming Languages and Systems, Vol. 7, No. 3, 1985, pp. 404-425.

Digital Library

[23]

G. Ricart and A.K. Agrawala, "An Optimal Algorithm for Mutual Exclusion in Computer Networks," Comm. ACM, Vol. 24, No. 1, Jan. 1981, pp. 9-17.

Digital Library

[24]

K.M. Chandy and J. Misra, "The Drinking Philosophers Problem," ACM Trans. Programming Languages and Systems, Vol. 6, No. 4, 1984, pp. 632-646.

Digital Library

Cited By

Castello JRedmond PKuper L(2024)Inductive Diagrams for Causal ReasoningProceedings of the ACM on Programming Languages10.1145/36498308:OOPSLA1(529-554)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649830
Sreekanti VWu CLin XSchleier-Smith JGonzalez JHellerstein JTumanov A(2020)CloudburstProceedings of the VLDB Endowment10.14778/3407790.340783613:12(2438-2452)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407836
Wu CSreekanti VHellerstein JMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Transactional Causal Consistency for Serverless ComputingProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389710(83-97)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389710
Show More Cited By

Index Terms

Logical Time: Capturing Causality in Distributed Systems
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs
2. Software and its engineering
  1. Software creation and management
    1. Software development process management
      1. Software development methods
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Logical Clock Requirements for Reverse Engineering Scenarios from a Distributed System

To reverse engineer scenarios from event traces, one must infer causal relationships between events. The inferences are usually based on a trace with sequence numbers or timestamps corresponding to some kind of logical clock. In practice, there is an ...
Logical Instantaneity and Causal Order: Two ``First Class'' Communication Modes for Parallel Computing
Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing

This paper focuses on two communication modes, namely Logically Instantaneity (LI) and Causal Order (CO). These communication modes address two different levels of quality of service in message delivery. LI means that it is possible to timestamp ...
Logical Time in Distributed Computing Systems
Distributed computing systems: separate resources acting as one

The partial ordering of events as defined by their causal relationships, that is, the ability of one event to directly, or transitively, affect another is defined. Its generalized and practical implementations in terms of partially ordered logical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer

Computer Volume 29, Issue 2

February 1996

78 pages

ISSN:0018-9162

Editor:
Edward A. Parrish
Worcester Polytechnic Institute, Worcester, MA

Issue’s Table of Contents

Copyright © Copyright © 1996 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 February 1996

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Castello JRedmond PKuper L(2024)Inductive Diagrams for Causal ReasoningProceedings of the ACM on Programming Languages10.1145/36498308:OOPSLA1(529-554)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649830
Sreekanti VWu CLin XSchleier-Smith JGonzalez JHellerstein JTumanov A(2020)CloudburstProceedings of the VLDB Endowment10.14778/3407790.340783613:12(2438-2452)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407836
Wu CSreekanti VHellerstein JMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Transactional Causal Consistency for Serverless ComputingProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389710(83-97)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389710
Bradbury MJhumka AMaple CZimmerling M(2019)The impact of decreasing transmit power levels on FlockLab to achieve a sparse networkProceedings of the 2nd Workshop on Benchmarking Cyber-Physical Systems and Internet of Things10.1145/3312480.3313171(7-12)Online publication date: 15-Apr-2019
https://dl.acm.org/doi/10.1145/3312480.3313171
Santana MSampaio AAndrade MRosa NHung CPapadopoulos G(2019)Transparent tracing of microservice-based applicationsProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297403(1252-1259)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297403
Korgaonkar KIzraelevitz JZhao JSwanson SRobinson PEllen F(2019)VorpalProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331598(435-444)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331598
Wu XLi CWang XYang H(2019)A Creative Approach to Reducing Ambiguity In Scenario-based Software Architecture AnalysisInternational Journal of Automation and Computing10.1007/s11633-017-1102-y16:2(248-260)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s11633-017-1102-y
Dokulil J(2019)Consistency model for runtime objects in the Open Community RuntimeThe Journal of Supercomputing10.1007/s11227-018-2681-275:5(2725-2760)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s11227-018-2681-2
Goldstein RKhan ADalle OWainer G(2018)Multiscale representation of simulated timeSimulation10.1177/003754971772686894:6(519-558)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1177/0037549717726868
Fouquet FHartmann TMosser SCordy MHaddad HWainwright RChbeir R(2018)Enabling lock-free concurrent workers over temporal graphs composed of multiple time-seriesProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167255(1054-1061)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167255
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents