Transcript Part 0

Lecture 1:
Logical and Physical Time
with some Applications
Anish Arora
CSE 6333
Notes include material from Dr. Jeff Brumfield
Required Reading
•
Time, Clocks, and the Ordering of Events
in a Distributed System
 by Leslie Lamport
 research.microsoft.com/users/lamport/pubs/time-clocks.pdf
•
Chapter 5 in Paul Sivilotti's book
Why Time Is Important
•
Scheduling of Requests
 Time-dependent policies such as FCFS
•
Prearranged Synchronization
 Set of processes perform action at give time
 Each process has time slice for activity
 One process begins at time another finishes
•
Multi-version Objects
 Latest timestamp implies newest version
•
Interpretation of Data
 Data that is a function of time (e.g., seismic data)
•
Timestamping Events
Motivation
Observer A: “star 1 exploded before star 2”
Observer B: “star 2 exploded before star 1”
Can the observers determine the truth?
What if the speed of light is not constant?
Ordering Events
What do we mean when we say that:
event A happened before event B?
•
•
Answer:
A happened at an earlier time than B
Problem: This definition requires clocks. Clocks aren't
perfectly accurate and don't keep precise physical time
Can we define the notion of “happened before” without using
clocks?
The “Happened Before” Relation
•
Event A happened before event B if
 1) A and B are events in the same process and
A came before B
 2) A is the sending of a message by one process and
B is the receipt of that message by another process
 3) A happened before C, and C happened before B
•
•
This definition assumes that a process is a set of events
with an a priori total ordering
If event A happened before event B then it is possible for
event A to causally affect event B
Concurrent Events
•
Events A and B are concurrent if
 1) A did not happen before B, and
 2) B did not happen before A
•
•
If two events are concurrent, then neither can causally
affect the other
Note that concurrency is not transitive. If A and B are
concurrent and B and C are concurrent, it does not
necessarily follow that A and C are concurrent
Space-Time Diagrams
Logical Clocks
•
•
•
A clock is a way of assigning a number to an event, where
the number is thought of as the time at which the event
occurred
Assume each process has a clock that assigns a number
to any event in that process. A clock could simply be a
counter
A system of clocks is said to be correct if it satisfies the
following condition:
 For any two events A and B, if A happened before B then
the time of event A is less than the time of event B
Implementing Logical Clocks
•
•
•
•
Each process maintains its own logical clock, which
assigns times to events in that process
Each process increments its logical clock between
successive events
Each message contains a timestamp whose value is the
time at which the message was sent
Upon receiving a message, a process sets its clock greater
than or equal to its present value and greater than the
timestamp
Logical Clocks
Ordering Events Totally
•
A system of logical clocks can be used to totally order the
set of all system events:
 Order the events by the times at which they occur
 Break ties using any total ordering of the processes (e.g.,
unique process numbers)
•
The total ordering depends on the system of clocks and
the tie breaking scheme. It is not unique
Anomalous Behavior
B's message may be given an earlier timestamp than A's,
even though A and B both know that A's message was
sent first