Lesson 2.4: Logical Clocks

What are logical clocks ?

Logical clocks are a concept used in distributed systems to order events without relying on physical time synchronization. They provide a way to establish a partial ordering of events based on causality rather than real-time clock values.

Causality

• In distributed systems, causality refers to the relationship between events where one event directly or indirectly influences another. Logical clocks are mechanisms used to capture and track these causal relationships without relying on physical time.
• Logical clocks help determine the happens-before relationship (denoted as →) between events in a distributed system, as defined by Leslie Lamport.

Happens-Before Relation (→):

• If A → B, then event A causally affects event B.
• This can be due to:
  • Same process: If A occurs before B in the same process.
  • Inter-process communication: If A is a message send and B is the corresponding receive.
  • Transitivity: If A → C and C → B, then A → B.

Logical Clocks (Lamport Clocks):

• Each process maintains a counter (logical timestamp).
• Rules:
  • Local event: Increment the clock.
  • Send message: Include current timestamp with the message.
  • Receive message: Update clock to max(local clock, received timestamp) + 1.
• If A → B, then L(A) < L(B), but the converse isn't always true.

Differences Between Physical and Logical Clocks

Physical clocks and logical clocks serve distinct purposes in distributed systems:

• Nature of Time:
  • Physical Clocks: These rely on real-world time measurements and are typically synchronized using protocols like NTP (Network Time Protocol). They provide accurate timestamps but can be affected by clock drift and network delays.
  • Logical Clocks: These are not tied to real-world time and instead use logical counters or timestamps to order events based on causality. They are resilient to clock differences between nodes but may not provide real-time accuracy.`
• Usage:
  • Physical Clocks: Used for tasks requiring real-time synchronization and precise timekeeping, such as scheduling tasks or logging events with accurate timestamps.
  • Logical Clocks: Used in distributed systems to order events across different nodes in a consistent and causal manner, enabling synchronization and coordination without strict real-time requirements.
• Dependency:
  • Physical Clocks: Dependent on accurate timekeeping hardware and synchronization protocols to maintain consistency across distributed nodes.
  • Logical Clocks: Dependent on the logic of event ordering and causality, ensuring that events can be correctly sequenced even when nodes have different physical time readings.

Lamport Logical Clocks

Lamport Logical Clocks are a mechanism to order events in a distributed system where there is no global clock. Each process maintains its own logical clock, which increments based on local events and message exchanges. Key Rules:

• Local Event:
  • Before an event occurs, increment the local clock:
  • LC = LC + 1
• Send Event:
  • Before sending a message, increment the local clock and attach the timestamp to the message.
  • LC = LC + 1
  • send(message, LC)
• Receive Event:
  • On receiving a message, update the local clock to be the maximum of the current clock and the received timestamp, then increment.
  • LC = max(LC, received_LC) + 1

Vector Clocks: Explained with Examples

Vector Clocks extend Lamport Logical Clocks to capture causality (happens-before relationships) more precisely in distributed systems. Unlike Lamport clocks (which only provide a partial order), vector clocks can determine if two events are concurrent or causally related.

How Vector Clocks Work?

• Each process maintains a vector (array) of integers, where:
  • V[i] = Number of events observed from process P_i.
• Rules:
  • Local Event: Increment your own component.
    • V[own_process_id] += 1
  • Send Message: Increment your own component and attach the vector to the message.
    • V[own_process_id] += 1
    • send(message, V)
  • Receive Message: Take the element-wise maximum and increment your own component.
    • V = [max(V_local[i], V_received[i]) for all i]
    • V[own_process_id] += 1