CoreConcept & Pseudocode Entry

Lamport Logical Clocks

Orders events across distributed processes without synchronized physical clocks using a monotonically increasing scalar logical counter.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Distributed Consensus
Difficulty: Beginner
Family: Distributed Consensus
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 2
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: Lamport Timestamps, Lamport Clock, Logical Clocks

Overview

Lamport Logical Clocks capture the causal happens-before relation (a -> b implies L(a) < L(b)) by incrementing a local counter on each event and updating L = max(L_local, L_msg) + 1 whenever a message is received.

Core Concepts

happens-before relationlogical timecausal orderingtie-breaking total order

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1) per event

Average

O(1) per event

Worst

O(1) per event

Space

O(1) per process

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Lamport Logical Clocks across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(1) per event

11 ns

Sub-microsecond~4

Est. Worst-Case TimeO(1) per event

11 ns

Sub-microsecond~4

Est. Working MemoryO(1) per process

128 B

L2/L3 Cache FriendlyN=100,000

When to Use

Scalar logical clock algorithm for ordering events in a distributed system without synchronized physical clocks, preserving the causal happens-before relation a -> b => L(a) < L(b).
Use Lamport Logical Clocks when you need a lightweight O(1)-space scalar timestamp consistent with causal happens-before ordering across distributed servers.
Use it with process-ID tie-breaking (L(a), pid) when you need a deterministic total order of events across a distributed cluster.

When Not to Use

Avoid Lamport scalar clocks when you must tell whether two events are causally related or concurrent (L(a) < L(b) does not imply a -> b); use Vector Clocks instead.

What It Does

Assigns scalar logical timestamps to distributed events
Guarantees that if event a causally precedes event b (a -> b), then L(a) < L(b)

Use Cases

Ordering events in distributed systems without synchronized physical wall clocks
Total ordering of broadcast requests in distributed mutual exclusion
Causal event logging across microservices and message queues

Inputs

Local process events and inter-process messages carrying sender timestamp L_msg

Outputs

Monotonically increasing logical timestamp L(e) for each event

Key Formulas (2)

Causal implication

a → b implies L(a) < L(b)

a -> b implies L(a) < L(b)

If event a causally precedes event b, its Lamport timestamp is strictly smaller.

Receive update rule

L_recv = max(L_local, L_msg) + 1

L_recv = max(L_local, L_msg) + 1

Advances the receiver's logical clock beyond both its local clock and the message timestamp.

Pseudocode

1.Initialize local logical clock L = 0 on each node
2.On local event or before sending a message: L = L + 1
3.Attach timestamp L_msg = L to the outgoing message
4.On receiving message with L_msg: L = max(L, L_msg) + 1
5.Break ties using (L, node_id) for a strict total order

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Initialize local logical clock L = 0 on each node
On local event or before sending a message: L = L + 1
Attach timestamp L_msg = L to the outgoing message
On receiving message with L_msg: L = max(L, L_msg) + 1
Break ties using (L, node_id) for a strict total order

Canonical Example

Input: Node A sends msg at L=1 to Node B (currently at L=3)
Output: Node B updates clock to max(3, 1) + 1 = 4
Explanation: Receiving a message advances the receiver clock past both its local history and the sender timestamp.

Implementation Notes

Each node maintains a single integer counter initialized to 0.
Attach the current counter value to every outgoing RPC or message.

Common Pitfalls

Assuming L(a) < L(b) means event a caused event b; Lamport clocks are only a one-way implication (a -> b => L(a) < L(b)).
Forgetting to increment the receiver's clock to max(local, received) + 1 on message receipt.