File: lamport-clocks/lamport.py

Date: 2026-05-29

Time: 08:57

lamport-clocks/lamport.py — Lamport Logical Clocks

Purpose

This file implements Lamport logical clocks and their primary application: distributed mutual exclusion. It's a reference implementation of two foundational algorithms from Leslie Lamport's 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System" — the logical clock protocol itself, and the mutex algorithm built on top of it. The file owns all event ordering logic: clock advancement, causal tracking via the happens-before relation, and total ordering of events across nodes.

Key Components

Data Classes

Event — Represents a single event (LOCAL, SEND, or RECEIVE) at a node. Beyond the visible fields (nodeid, eventtype, timestamp, description, message_id), it carries two hidden graph edges:

• _parent: links to the previous event on the same node (intra-process ordering)
• _cause: links a RECEIVE event back to the corresponding SEND event (inter-process causality)

These two edges form the happens-before graph that _reaches() traverses.

Message — A simple envelope carrying senderid, sendertimestamp, message_id, and payload. The timestamp piggybacks on the message so the receiver can update its clock.

LamportClock

A single integer counter with three operations:

• tick() — Increment for local events. Returns the new value.
• send_tick() — Identical to tick(). Exists as a separate method for semantic clarity (the Lamport protocol treats send as "increment then stamp").
• receivetick(receivedtimestamp) — The core Lamport rule: counter = max(local, received) + 1. This is what ensures causal consistency — a receive event always has a timestamp strictly greater than the corresponding send.

Node

A process in the distributed system. Each node owns a LamportClock and an append-only eventlog. The three event methods mirror the three clock operations:

• localevent(description) — Ticks the clock, appends a LOCAL event with parent pointing to the previous event on this node.
• sendmessage(tonode, payload) — Ticks the clock, records a SEND event, creates a Message, and delivers synchronously by calling tonode.receivemessage(). This is a simplification — real systems would queue and deliver asynchronously.
• receivemessage(message, sendevent) — Applies receivetick, records a RECEIVE event with both parent (previous local event) and cause (the send event that produced this message).

LamportMutex

Implements Lamport's distributed mutex algorithm. The protocol:

1. request(node) — The requesting node ticks its clock, adds (timestamp, node_id) to the shared request queue, then broadcasts REQUEST messages to all other nodes. Each recipient immediately sends an ACK back. The mutex tracks which ACKs have been received per requesting node.

2. can_enter(node) — A node can enter the critical section when:

• Its own request is at the head of the queue (lowest (timestamp, node_id))
• It has received ACKs from all other nodes

3. release(node) — Removes the node's request from the queue and broadcasts RELEASE to all others.

The request queue is sorted by (timestamp, node_id), which gives a deterministic total order even when timestamps collide.

Free Functions

totalorder(events) — Sorts events by (timestamp, nodeid). This is the standard Lamport total order — timestamps provide causal ordering, node IDs break ties deterministically.

happensbefore(eventa, eventb, allevents) — Determines the causal relationship: True if a→b, False if b→a, None if concurrent. Note that the allevents parameter is accepted but unused — the implementation relies entirely on the parent/_cause graph edges.

reaches(source, target) — BFS backward from target through parent and _cause edges to check if source is reachable. This is the operational definition of happens-before: a→b iff there's a path from a to b in the causal graph.

Patterns

• Causal graph via hidden fields: The parent and cause fields on Event are excluded from repr (via field(repr=False)) and form an implicit DAG. This separates the causal structure (used by happens_before) from the observable event data.

• Synchronous message delivery: sendmessage calls receivemessage directly, making the simulation deterministic and single-threaded. The sendevent parameter threads the causal link through the delivery.

• Global message counter: msgcounter = itertools.count(1) is module-level state that generates unique message IDs across all nodes. This avoids coordination but means message IDs are tied to execution order.

• Centralized mutex state: The LamportMutex holds the request queue and ACK tracking in a single object, simulating what would be replicated state in a real distributed system. Each node would maintain its own copy of the queue in practice.

Dependencies

Imports: Standard library only — dataclasses, typing, collections.deque, itertools. No external dependencies.

Imported by: test_lamport.py — the test suite that exercises clock behavior, message passing, mutex correctness, and happens-before reasoning.

Flow

A typical interaction:

1. Create several Node instances

2. Nodes perform local_event() calls (clock ticks: 1, 2, 3...)

3. Node A calls send_message(B, "hello"):

• A's clock ticks (e.g., to 4), SEND event recorded
• Message(senderid="A", sendertimestamp=4, ...) created
• B's receive_message called immediately
• B's clock becomes max(Bclock, 4) + 1, RECEIVE event recorded with cause pointing to A's SEND event

4. total_order() can sort all events from all nodes into a single consistent sequence

5. happensbefore() can determine if any two events are causally related by walking the parent/_cause graph

For mutual exclusion, the flow adds:

1. Wrap nodes in a LamportMutex

2. mutex.request(node) broadcasts REQUEST, collects ACKs

3. mutex.can_enter(node) checks queue head + ACK completeness

4. After critical section work, mutex.release(node) broadcasts RELEASE

Invariants

• Lamport clock monotonicity: A node's clock never decreases. tick() and sendtick() always increment; receivetick() takes max + 1, which is always ≥ current + 1.
• Causal consistency: If event a causally precedes event b, then a.timestamp < b.timestamp. This is guaranteed by receive_tick using max(local, sender) + 1.
• The converse does NOT hold: a.timestamp < b.timestamp does not imply a→b. Two concurrent events can have ordered timestamps. This is a fundamental limitation of Lamport clocks (vector clocks address it).
• Mutex safety: can_enter requires both (1) the node's request is the queue minimum and (2) all other nodes have ACKed. Together these guarantee mutual exclusion — at most one node can satisfy both conditions simultaneously.
• Total order determinism: Ties in timestamp are broken by node_id string comparison, giving a total order consistent across all nodes.

Error Handling

There is essentially none. The code assumes:

• Nodes passed to send_message are valid and reachable
• Messages are never lost or duplicated (synchronous delivery guarantees this)
• receive_tick always receives a non-negative integer
• The mutex is used correctly (request before can_enter, release after entering)

No exceptions are raised or caught anywhere. This is appropriate for a reference implementation — it models the algorithm's happy path, not network failure modes.

Topics to Explore

• [file] vector-clocks/vector_clock.py — The natural successor to Lamport clocks; vector clocks can distinguish concurrent events from causally ordered ones, fixing the "converse doesn't hold" limitation
• [file] lamport-clocks/test_lamport.py — See how the happens-before relation and mutex are tested; reveals edge cases the implementation handles
• [function] lamport-clocks/lamport.py:_reaches — The BFS graph traversal is the computational core of happens-before detection; understanding its performance characteristics matters for large event histories
• [general] lamport-1978-paper — Lamport's original "Time, Clocks, and the Ordering of Events in a Distributed System" paper, which this code directly implements
• [file] total-order-broadcast/totalorderbroadcast.py — Total order broadcast builds on the same clock-based ordering ideas to deliver messages in a consistent sequence across nodes

Beliefs

• lamport-receive-tick-guarantees-causal-order — receive_tick computes max(local, received) + 1, ensuring every receive event has a timestamp strictly greater than the corresponding send event
• lamport-happens-before-uses-graph-not-timestamps — happensbefore() determines causality by BFS over parent/cause edges, not by comparing timestamps; the allevents parameter is accepted but never used
• lamport-mutex-requires-all-acks — can_enter() returns True only when the node's request is at the queue head AND acknowledgments have been received from every other node in the system
• lamport-send-delivers-synchronously — sendmessage calls tonode.receive_message() directly in the same call stack, making message delivery instantaneous and deterministic (no async queue or network simulation)
• lamport-total-order-breaks-ties-by-node-id — totalorder() sorts by (timestamp, nodeid), using lexicographic node ID comparison as a deterministic tiebreaker when timestamps are equal