Logical Clock
Logical clocks: Lamport timestamps and vector clocks.
A logical clock is a mechanism used in distributed systems to track the ordering of events without relying on physical time. Instead of measuring real time, logical clocks measure event relationships.
Logical Clock
Did event A happen before event B?
Lamport Logical Clock
A Lamport clock is a logical clock that assigns a numerical timestamp to events to preserve their causal ordering. Each process keeps a counter.
# Rules 1. Before every event increment the count example: A event -> count 0 A event -> count 1 2. When sending a message attach the timestamp example: Send message with timestamp = 2 3. When receiving a message update the clock with this formula clock = max(local_clock, received_timestamp) + 1 example: B clock = max(0,2) + 1 B clock = 3
Event started
now, rule max(0,2)+1=3
(2,5) + 1 = 6
Problem: Lamport clocks cannot detect concurrency. Example: Event A → timestamp 5 Event B → timestamp 6 We cannot say: A happened before B or B happened before A They might be independent.
Vector Clock
A vector clock is a logical clock that tracks causality between events using a vector (array) of counters, where each counter represents a process in the system. Instead of storing one number, we store a list of numbers.
# Assumptions we have 3 machine A = [0,0,0] B = [0,0,0] c = [0,0,0] # Rules 1. Before every event increment the count of that node index in your node vector example: event in A -> [1,0,0] 2. When sending a message attach the timestamp and increment the counter example: Send message with timestamp A = [2,0,0] 3. When receiving a message Take element-wise max of both vectors and increment the count VC[i] = max(local[i], received[i]) example: B = [2,0,0] -> [2,1,0] A = [2,0,0] B = [0,0,0] B = [max(2,0),max(0,0),max(0,0)] = [2,0,0] + 1 = [2,1,0] Comparision: Event X → [2,1,0] Event Y → [3,1,0] x < y Event A → [2,1,0] Event B → [1,2,0] A || B