Logical time: capturing causality in distributed systems

Publisher Website
Google Scholar
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.

This publication has 20 references indexed in Scilit: