LOGICAL TIME - CAPTURING CAUSALITY IN DISTRIBUTED SYSTEMS

A distributed computation consists of a set of processes chat cooperat e and compete to achieve a common goal. These processes do not share a common global memory and communicately solely by passing messages com munication network. The communication delay is finite but unpredictabl e. 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 depende ncy from the sender process to the receiver process. Consequently, the execution of a distributed application results in a set of distribute d events produced by the process. The causal precedence relation induc es a partial order on the events of a distributed computation. Causali ty among events, more formally the causal precedence relation, is a po werful 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 t ime is basic to capturing the causality between events. Distributed sy stems have no built-in physical time and can only approximate it. Howe ver, in a distributed computation, both the progress and the interacti on 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 clock s in distributed systems and discusses three methods-scalar, vector, a nd matrix-for implementing logical time in these systems.