Chapter 3 - Logical Time Notes | EduRev

: Chapter 3 - Logical Time Notes | EduRev

 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 / 67
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!