Happens-Before and the Scalar Logical Clock

Two events in a distributed system are ordered by causality when one could have influenced the other. That is a weaker relation than “one happened before the other in real time”, and it has the considerable advantage of being observable from inside the system. The relation Lamport defined in 1978 is built from three rules about a single process and its messages, and it needs no clock at all.

The relation, stated without time

Fix a set of processes. Each process executes a sequence of events; a step of computation, the sending of a message, and the receipt of a message are all events. The relation → is the smallest relation satisfying:

1. If a and b are events in the same process and a comes before b in that process’s execution, then a → b.
2. If a is the sending of a message and b is the receipt of that same message, then a → b.
3. If a → b and b → c, then a → c.

Two distinct events a and b are concurrent, written a ∥ b, when neither a → b nor b → a. Concurrency here is a technical term, not a claim that the events happened at the same moment. It means the system has no evidence of an ordering between them: no chain of program order and message delivery connects the two.

This is a strict partial order. It is irreflexive, asymmetric, and transitive, and it is not total, because concurrent pairs exist. In any real execution with more than one process, concurrency is the common case rather than an edge case.

The definition deliberately ignores real time. If a → b, then a did happen before b in real time, since a message cannot be received before it is sent and a process executes one event at a time. The converse does not hold. Two events on different machines can be ordered by the physical clock and still be concurrent, and that gap is where wall-clock reasoning fails, as described in Wall-Clock Timestamps Do Not Order Distributed Events.

One integer per process

Lamport’s construction attaches a counter to each process. The rules are as mechanical as the relation:

• Each process maintains a local counter, initialized to zero.
• Before executing any event, the process increments its counter.
• When a process sends a message, it attaches the current counter value to the message.
• When a process receives a message carrying value t, it sets its counter to max(local, t) + 1 before treating the receipt as an event.

The resulting assignment satisfies the clock condition: for any events a and b, if a → b then C(a) < C(b). The proof is a case analysis on the three rules. Program order holds because the counter strictly increases before each event. Message order holds because the receiver’s counter is raised above the sender’s before the receive event is stamped, so the receive is strictly greater than the send. Transitivity follows from transitivity of < on integers.

type Clock struct {
	mu sync.Mutex
	t  uint64
}

// Tick stamps a local event.
func (c *Clock) Tick() uint64 {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.t++
	return c.t
}

// Send stamps an outgoing message and returns the timestamp to attach.
func (c *Clock) Send() uint64 { return c.Tick() }

// Receive merges an incoming timestamp, then stamps the receive event.
func (c *Clock) Receive(remote uint64) uint64 {
	c.mu.Lock()
	defer c.mu.Unlock()
	if remote > c.t {
		c.t = remote
	}
	c.t++
	return c.t
}

The merge step is the whole of the algorithm. It is a join on the max of two integers followed by an increment, and the increment is what makes the receive strictly later than the send rather than merely not earlier.

The converse fails, and that matters

The clock condition is an implication, not an equivalence. C(a) < C(b) does not imply a → b. Two processes that never exchange messages will both produce timestamps 1, 2, 3, … and a pair of events stamped 2 and 3 may be entirely unrelated. The scalar clock therefore compresses the partial order into a total order on integers and loses the information about which pairs were concurrent.

That loss is exactly why a scalar clock cannot answer the question “are these two writes conflicting”. A store that compares Lamport timestamps can pick a winner, but it cannot distinguish “the second write happened after the first and supersedes it” from “the two writes were concurrent and the tie-break chose one arbitrarily”. Detecting concurrency requires a value whose comparison is partial, which is what vector clocks provide at the cost of one counter per process.

The single integer is still enough for a weaker but often sufficient purpose: producing a total order consistent with causality. Sort by counter value and break ties by process identifier. Because the counter comparison respects →, any two causally related events appear in the correct relative position; concurrent events are ordered arbitrarily but consistently across all observers, since every observer sees the same (counter, id) pairs.

Where the total order is used

Lamport’s paper applies the order to a distributed mutual exclusion protocol. Every process keeps a queue of requests ordered by logical timestamp. To enter the critical section, a process broadcasts a request stamped with its counter and waits until it has received a reply from every other process and its own request is at the head of its queue. The reply rule is what makes the protocol work: a process replies immediately to a request with a larger timestamp, but defers its reply to a request with a smaller timestamp until it has itself entered and left the critical section. The deferred reply enforces the ordering that the timestamp claims.

The protocol costs 3(n-1) messages for n processes per critical-section entry, counting the request, the reply, and the release, and it requires every process to hear every request, so it fails under a partition rather than degrading. Its importance is conceptual: a total order derived from logical clocks is sufficient to implement mutual exclusion, and the same construction underlies replicated state machines, where every replica applies commands in the order the log assigns.

A second use is timestamping for conflict resolution. A register that stores (value, counter, writer) and overwrites only when the incoming timestamp is greater implements a deterministic merge that never depends on physical clocks. The merge is not necessarily semantically correct, since it will overwrite one of two concurrent writes, but it is at least stable: every replica that sees the same set of writes computes the same result.

Bounded counters and long-lived systems

The counter is an unsigned integer and it grows with every event and every merge. At a million events per second, a 64-bit counter would take centuries to exhaust, so overflow is not a practical concern for uint64. It is a concern for the wire format: a protocol that allocates 32 bits to a logical timestamp and runs at high event rates exhausts the space in the range of hours to days depending on rate, and the usual repair is to widen the field or to piggyback a coarse physical time so that counters can be reset per epoch.

There is a subtler failure in systems that persist the counter. If a process crashes and restarts with a counter read from durable storage that was written before the crash, events that happened just before the crash may carry larger values than events after the restart. The fix is to persist the counter with the same durability as the state it stamps, or to advance it past any value that could have been issued, which usually means a conservative jump on restart.

Lamport’s contribution was to show that ordering does not require timekeeping, only communication. The scalar clock is the cheapest possible encoding of that insight: one integer per process, one comparison per message. Its price is that it cannot distinguish concurrency from causality, and the next step in the cluster is to pay for that distinction.