UNIT II

LOGICAL TIME AND GLOBAL STATE

Logical Time: Physical Clock Synchronization: NTP – A Framework for a System of Logical
Clocks – Scalar Time – Vector Time; Message Ordering and Group Communication: Message
Ordering Paradigms – Asynchronous Execution with Synchronous Communication –
Synchronous Program Order on Asynchronous System – Group Communication – Causal
Order – Total Order; Global State and Snapshot Recording Algorithms: Introduction – System
Model and Definitions – Snapshot Algorithms for FIFO Channels.

Logical Time
Logical time is used to order events in a system where there is no global clock.
Unlike physical time (like NTP), logical time does not depend on real-world
timestamps—it’s all about causality (what happened before what).
Why Logical Time?
In a distributed system:
●​ Machines have separate clocks.
●​ Synchronizing all clocks perfectly is impossible.
●​ So, we care more about the order of events than their exact timestamps.

Key Concepts
1. Happened - Before Relation (→)
Introduced by Leslie Lamport:
●​ If Event A → Event B, then A happened before B.
●​ This forms a partial ordering of events.

2. Lamport Timestamps
●​ Each process maintains a logical clock (LC) (just a number).
●​ Rules:
1.​ Before executing an event, increment LC by 1.
2.​ When sending a message, attach the current LC.
3.​ On receiving a message, set
LC = max (LC, timestamp from sender) + 1.
●​ This ensures a consistent ordering:​
If A → B, then timestamp(A) < timestamp(B).
3. Vector Clocks
●​ A more accurate model of causality than Lamport clocks.
●​ Each process maintains a vector of clocks (one for every process).
●​ When events or messages happen, the vector is updated.
●​ Helps detect concurrent events.
Example
Imagine two processes:
●​ P1 sends a message to P2.
●​ Using Lamport clocks:​
So A → B (A happened before B).
Use in Distributed Systems
●​ Ordering logs/events (e.g., in distributed databases
●​ Detecting causality and concurrency
●​ Snapshot algorithms
●​ Deadlock detection

Physical Clock Synchronization

In distributed systems, each computer (node) has its own hardware
clock, and these clocks can drift apart over time due to hardware differences.
To ensure consistency, physical clock synchronization is used.
Why Synchronize Clocks?
●​ To order events correctly across systems.
●​ Needed in applications like distributed databases, logging, transactions,
scheduling, etc.
●​ Real-world example: Booking a train ticket—time consistency across
servers is crucial.
Types of Physical Clock Synchronization
1. Cristian’s Algorithm
●​ Uses a time server to synchronize.
●​ Assumes symmetric network delay.
●​ Steps:
1.​ Client sends request to time server.
2.​ Server replies with current time.
3.​ Client sets its clock to
T_server + (round-trip delay / 2).
Limitation: Assumes network delay is symmetrical (which is not always true).
2. Berkeley Algorithm
●​ Suitable for systems without an accurate external time source.
●​ A master polls time from all nodes, calculates average, and sends
adjustments.
●​ Steps:
1.​ The master asks all nodes for their clock times.
2.​ It calculates the average time.
3.​ Sends offsets to each node, not the exact time.
4.​ Each node adjusts its clock.
Advantage: Works even if no node has accurate time.
3. Network Time Protocol (NTP)
●​ Most widely used internet-scale clock synchronization protocol.
●​ Uses a hierarchy of time servers (stratum levels).
●​ Synchronizes clocks with millisecond to microsecond accuracy.
●​ Supports delay compensation and drift adjustment.​

NTP Architecture:
Stratum 0: Atomic Clock, GPS
↓
Stratum 1: Time servers synced to stratum 0
↓
Stratum 2: Servers synced to stratum 1, and so on...
↓
Client machines
Network Time Protocol (NTP)
●​ NTP is used for clock synchronization using a hierarchical architecture.
●​ Top-level servers in the hierarchy are connected to a UTC time source.
●​ It enables clients across the Internet to synchronize their clocks accurately with
UTC.
Three modes of NTP server synchronization:
1.​ Multicast mode
2.​ Procedure - call mode
3.​ Symmetric mode
(i) Multicast Mode:
●​ One or more servers periodically multicast the time to servers running on other
computers connected via LAN.
●​ These other computers set their clocks assuming a small delay.
●​ Accuracy is low in this mode — it achieves only limited precision.
(ii) Procedure-call mode:
●​ This mode is similar to Cristian’s algorithm.
●​ A server accepts time requests from other computers.
●​ It replies with its current timestamp.
●​ This mode is suitable for higher accuracy compared to multicast mode.
(iii) Symmetric Mode:
●​ In this mode, two NTP servers exchange time synchronization information with
each other.
●​ Both servers act as both clients and servers simultaneously.
●​ Each server sends time to the other and uses the received information to
synchronize their clocks.
A Framework for a System of Logical Clocks
(i) Clock:
●​ A logical clock Cp​ of a process p, is a software counter.
●​ It is used to timestamp events executed by process p, ensuring it follows the
happens-before relation.
●​ It is used to represent the ordering of events based on their causal relationships.
(ii) Timestamps:
●​ Timestamps are assigned to each event by the logical clock.
●​ Each event is given a unique timestamp.
●​ These timestamps are used to order events.
Properties:
1.​ Consistency:
ei→ej⇒C(ei)<C(ej)
○​ If event ei​ happens-before event ej​, then the timestamp of ei​ is less than that of
ej​.
○​ Ensures causal ordering is preserved.​

2.​ Strong Consistency:

ei→ej⇔C(ei)<C(ej)
○​ If and only if C(ei)<C(ej), then ei​ happens-before ej​.
○​ This is a stricter condition and ensures timestamps fully reflect causality.
(iii) Clock Synchronization:
●​ It is the process of ensuring that all clocks in the system are consistent with one
another.
●​ This helps in maintaining a uniform sense of time across distributed processes.
(iv) Event Ordering:
●​ This is the process of determining the sequence in which events occurred in the
system.
●​ Essential for ensuring causality and coordination among distributed processes.
(v) Implementation:
●​ Each node initializes its logical clock to a starting value.
●​ Each node assigns a timestamp to every event using its logical clock.
●​ Nodes synchronize their clocks using a clock synchronization algorithm.
●​ Nodes use the timestamps to determine the order of events.

Scalar Time (Lamport Timestamp)

●​ The Lamport algorithm is used to synchronize logical clocks.
●​ The goal is to assign totally ordered timestamps to events (ensuring event order
across processes).
Steps:
1.​ All processes use a counter (clock) initialized to 0.
2.​ The counter is incremented and assigned to each event as its timestamp.
3.​ A send event carries its timestamp with the message.
4.​ For a receive event, the timestamp is updated as:
max(receiver-counter, message-timestamp)+1
Lamport Scalar Time Rules Recap:
1.​ Increment Rule (Rule 1):​
Every process increments its clock between events (e.g., local computation).
2.​ Send Rule (Rule 2):​
When a process sends a message, it sends its current time stamp with the
message.
3.​ Receive Rule (Rule 3):​
When a process receives a message, it updates its clock to be greater than the
maximum of its current clock and the received timestamp.

Message Passing (with timestamp sync):

1.​ P1 (2) → P2 (3)
○​ P1 sends message at timestamp 2
○​ P2 receives and sets its clock to max(2, 2) + 1 = 3
2.​ P2 (4) → P3 (5)
○​ P2 sends at 4, P3 updates its clock to max(1, 4) + 1 = 5
3.​ P3 (7) → P1 (8)
○​ P3 sends at 7, P1 updates to max(3, 7) + 1 = 8
4.​ P1 (9) → P2 (10)
○​ P1 sends at 9, P2 updates to max(5, 9) + 1 = 10
Requirements of Scalar Time:
1.​ Causal Consistency​
If a → b (i.e., event a happens-before event b), then​
T(a)<T(b)T(a) < T(b)T(a)<T(b)
2.​ Uniqueness​
Timestamps of any two different events must not be equal:​
T(a)≠T(b)T(a) \neq T(b)T(a)=T(b)
Properties of Scalar Time:
●​ Consistency:
If ei→ej​, then C(ei​)<C(ej​)​
(i.e., Lamport timestamps respect causal ordering).
●​ Total Ordering:​
All events in the system are totally ordered using scalar timestamps, even if they
are concurrent (by breaking ties arbitrarily, e.g., by process ID).
●​ Event Ordering:​
Events can be arranged linearly, though this does not imply causality for all
ordered pairs.
●​ Limitation:​
Scalar time is not strongly consistent. That is,​
T(a)<T(b)does not imply a→b
So, it can't distinguish between causally related and concurrent events.
Vector Time ( Vector Timestamp)
●​ A vector clock for a system of n processes is an array of n logical clocks,
with:
○​ One clock per process
○​ Each clock tracks its own local time and the latest known time of all other
processes
●​ Purpose:​
Vector clocks are used to determine whether two events are causally related.
Why Vector Clocks?
●​ Scalar clocks ensure total ordering but not causal accuracy.
●​ Vector clocks allow systems to check if:
○​ a→b (a happened-before b)
○​ a∥b (a and b are concurrent)
Rules:
1.​ Initialization: All clocks start at [0 0 0].
2.​ Internal event: Increment own clock:​
e.g., P1 does [1 0 0] → [2 0 0] → [3 0 0], etc.
3.​ Send message:​
Before sending, increment own clock and attach the vector.
4.​ Receive message:​
On receiving a vector [a b c], update own vector as:​
new[i] = max(current[i], received[i]) for all i,​
then increment own clock.

Steps to Maintain Vector Clocks:

1.​ Initialization:
○​ All vector clock values start at zero.
○​ For n processes, each process Pᵢ maintains a vector Vᵢ of size n.
2.​ Internal Event:
○​ When a process performs an internal event, it increments its own clock in the
vector.
3.​ Sending a Message:
○​ Before sending a message, a process increments its own clock and sends a copy of
its vector.
4.​ Receiving a Message:
○​ When a process receives a message with vector V_m, it:
■​ Increments its own clock:
■​ Updates each element of its vector with the max of the local and received
vector.