Page 1 Chapter 3: Logical Time Ajay Kshemkalyani and Mukesh Singhal Distributed Computing: Principles, Algorithms, and Systems Cambridge University Press A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 1 / 67 Page 2 Chapter 3: Logical Time Ajay Kshemkalyani and Mukesh Singhal Distributed Computing: Principles, Algorithms, and Systems Cambridge University Press A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 1 / 67 Distributed Computing: Principles, Algorithms, and Systems 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. In distributed systems, it is not possible to have a global physical time. As asynchronous distributed computations make progress in spurts, the logical time is su?cient to capture the fundamental monotonicity property associated with causality in distributed systems. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 2 / 67 Page 3 Chapter 3: Logical Time Ajay Kshemkalyani and Mukesh Singhal Distributed Computing: Principles, Algorithms, and Systems Cambridge University Press A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 1 / 67 Distributed Computing: Principles, Algorithms, and Systems 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. In distributed systems, it is not possible to have a global physical time. As asynchronous distributed computations make progress in spurts, the logical time is su?cient to capture the fundamental monotonicity property associated with causality in distributed systems. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 2 / 67 Distributed Computing: Principles, Algorithms, and Systems Introduction This chapter discusses three ways to implement logical time - scalar time, vector time, and matrix time. Causality 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, such as distributed algorithms design, tracking of dependent events, knowledge about the progress of a computation, and concurrency measures. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 3 / 67 Page 4 Chapter 3: Logical Time Ajay Kshemkalyani and Mukesh Singhal Distributed Computing: Principles, Algorithms, and Systems Cambridge University Press A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 1 / 67 Distributed Computing: Principles, Algorithms, and Systems 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. In distributed systems, it is not possible to have a global physical time. As asynchronous distributed computations make progress in spurts, the logical time is su?cient to capture the fundamental monotonicity property associated with causality in distributed systems. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 2 / 67 Distributed Computing: Principles, Algorithms, and Systems Introduction This chapter discusses three ways to implement logical time - scalar time, vector time, and matrix time. Causality 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, such as distributed algorithms design, tracking of dependent events, knowledge about the progress of a computation, and concurrency measures. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 3 / 67 Distributed Computing: Principles, Algorithms, and Systems A Framework for a System of Logical Clocks De?nition A system of logical clocks consists of a time domain T and a logical clock C. Elements of T form a partially ordered set over a relation <. Relation < is called the happened before or causal precedence. Intuitively, this relation is analogous to the earlier than relation provided by the physical time. The logical clock C is a function that maps an event e in a distributed system to an element in the time domain T, denoted as C(e) and called the timestamp of e, and is de?ned as follows: C : H 7? T such that the following property is satis?ed: for two events e i and e j , e i ? e j =? C(e i ) < C(e j ). A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 4 / 67 Page 5 Chapter 3: Logical Time Ajay Kshemkalyani and Mukesh Singhal Distributed Computing: Principles, Algorithms, and Systems Cambridge University Press A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 1 / 67 Distributed Computing: Principles, Algorithms, and Systems 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. In distributed systems, it is not possible to have a global physical time. As asynchronous distributed computations make progress in spurts, the logical time is su?cient to capture the fundamental monotonicity property associated with causality in distributed systems. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 2 / 67 Distributed Computing: Principles, Algorithms, and Systems Introduction This chapter discusses three ways to implement logical time - scalar time, vector time, and matrix time. Causality 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, such as distributed algorithms design, tracking of dependent events, knowledge about the progress of a computation, and concurrency measures. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 3 / 67 Distributed Computing: Principles, Algorithms, and Systems A Framework for a System of Logical Clocks De?nition A system of logical clocks consists of a time domain T and a logical clock C. Elements of T form a partially ordered set over a relation <. Relation < is called the happened before or causal precedence. Intuitively, this relation is analogous to the earlier than relation provided by the physical time. The logical clock C is a function that maps an event e in a distributed system to an element in the time domain T, denoted as C(e) and called the timestamp of e, and is de?ned as follows: C : H 7? T such that the following property is satis?ed: for two events e i and e j , e i ? e j =? C(e i ) < C(e j ). A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 4 / 67 Distributed Computing: Principles, Algorithms, and Systems A Framework for a System of Logical Clocks This monotonicity property is called the clock consistency condition. When T and C satisfy the following condition, for two events e i and e j , e i ? e j ? C(e i ) < C(e j ) the system of clocks is said to be strongly consistent. Implementing Logical Clocks Implementation of logical clocks requires addressing two issues: data structures local to every process to represent logical time and a protocol to update the data structures to ensure the consistency condition. Each process p i maintains data structures that allow it the following two capabilities: ? A local logical clock, denoted by lci, that helps process pi measure its own progress. A. Kshemkalyani and M. Singhal (Distributed Computing) Logical Time CUP 2008 5 / 67Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!