Book contents
- Frontmatter
- Contents
- Preface
- 1 Introduction
- 2 A model of distributed computations
- 3 Logical time
- 4 Global state and snapshot recording algorithms
- 5 Terminology and basic algorithms
- 6 Message ordering and group communication
- 7 Termination detection
- 8 Reasoning with knowledge
- 9 Distributed mutual exclusion algorithms
- 10 Deadlock detection in distributed systems
- 11 Global predicate detection
- 12 Distributed shared memory
- 13 Checkpointing and rollback recovery
- 14 Consensus and agreement algorithms
- 15 Failure detectors
- 16 Authentication in distributed systems
- 17 Self-stabilization
- 18 Peer-to-peer computing and overlay graphs
- Index
3 - Logical time
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- 1 Introduction
- 2 A model of distributed computations
- 3 Logical time
- 4 Global state and snapshot recording algorithms
- 5 Terminology and basic algorithms
- 6 Message ordering and group communication
- 7 Termination detection
- 8 Reasoning with knowledge
- 9 Distributed mutual exclusion algorithms
- 10 Deadlock detection in distributed systems
- 11 Global predicate detection
- 12 Distributed shared memory
- 13 Checkpointing and rollback recovery
- 14 Consensus and agreement algorithms
- 15 Failure detectors
- 16 Authentication in distributed systems
- 17 Self-stabilization
- 18 Peer-to-peer computing and overlay graphs
- Index
Summary
Introduction
The concept of causality between events is fundamental to the design and analysis of parallel and distributed computing and operating systems. Usually causality is tracked using physical time. However, in distributed systems, it is not possible to have global physical time; it is possible to realize only an approximation of it. As asynchronous distributed computations make progress in spurts, it turns out that the logical time, which advances in jumps, is sufficient to capture the fundamental monotonicity property associated with causality in distributed systems. This chapter discusses three ways to implement logical time (e.g., scalar time, vector time, and matrix time) that have been proposed to capture causality between events of a distributed computation.
Causality (or the causal precedence relation) among events in a distributed system is a powerful concept in reasoning, analyzing, and drawing inferences about a computation. The knowledge of the causal precedence relation among the events of processes helps solve a variety of problems in distributed systems. Examples of some of these problems is as follows:
Distributed algorithms design The knowledge of the causal precedence relation among events helps ensure liveness and fairness in mutual exclusion algorithms, helps maintain consistency in replicated databases, and helps design correct deadlock detection algorithms to avoid phantom and undetected deadlocks.
[…]
- Type
- Chapter
- Information
- Distributed ComputingPrinciples, Algorithms, and Systems, pp. 50 - 86Publisher: Cambridge University PressPrint publication year: 2008
- 1
- Cited by