Distributed systems do not have one obvious order of events. A message may be delayed, a process may pause, and two nodes may perform updates without knowing about each other. Physical clocks help humans reason about logs, but they cannot prove causality unless the system has strong synchronization guarantees. Lamport timestamps and vector clocks solve the ordering problem from inside the distributed computation itself.
Lamport’s 1978 paper introduced the happens-before relation: events are ordered when they occur in one process sequence, when one sends a message that another receives, or by transitivity. A scalar Lamport clock assigns an integer to every event so that if event A happened before event B, A’s timestamp is smaller than B’s. That is enough to build a deterministic total order by adding a process-id tie breaker, but it cannot tell whether two events were truly concurrent.
Vector clocks extend the idea by carrying one counter per participant. They preserve enough information to compare causal histories directly: one vector is before another if every component is less than or equal and at least one is strictly smaller. If neither vector dominates the other, the events are concurrent. This is why Dynamo-style databases can return siblings for application reconciliation instead of silently overwriting one concurrent write with another.
The practical lesson is narrow but important: use scalar logical clocks when you need a cheap causal-respecting order, use vector clocks when you must detect concurrency, and use hybrid logical clocks only when you also need timestamps close to wall-clock time.
Happens-before is a partial order over events. Within one process, earlier local events happen before later local events. A send happens before the matching receive. If A happens before B and B happens before C, then A happens before C. Events that cannot be connected through those rules are concurrent, even if wall-clock timestamps appear to put one earlier than the other.
Each process keeps a counter. It increments the counter before each local event and attaches the counter to outgoing messages. On receive, it sets its counter to at least the received timestamp plus one. This satisfies Lamport’s clock condition: causal order implies timestamp order. The converse is false, so a smaller Lamport timestamp does not prove causality.
A vector clock stores a map from replica identity to counter. A process increments its own component on local events and merges received vectors component-wise using maximum. This gives a compact causal summary of the event’s known past. For a fixed membership set of N replicas, each timestamp has O(N) components.
Lamport clocks can impose a total order by sorting on (timestamp, process_id), but that order may arbitrarily order concurrent events. Vector clocks preserve the partial order so the system can distinguish “definitely older”, “definitely newer”, and “concurrent, needs merge”.
The scalar algorithm is cheap: one integer per process and one integer per message. It is useful for log ordering, deterministic request queues, and protocols that need all nodes to break ties the same way after causality has been respected.
type LamportClock struct {
node string
t uint64
}
func (c *LamportClock) Tick() uint64 {
c.t++
return c.t
}
func (c *LamportClock) Send() uint64 {
return c.Tick()
}
func (c *LamportClock) Receive(messageTime uint64) uint64 {
if messageTime > c.t {
c.t = messageTime
}
c.t++
return c.t
}
func Less(aTime uint64, aNode string, bTime uint64, bNode string) bool {
if aTime != bTime {
return aTime < bTime
}
return aNode < bNode
}Vector clocks need a merge operation and a comparison operation. Merge takes the component-wise maximum. Compare returns before, after, equal, or concurrent. The concurrent case is the value that scalar clocks cannot represent.
type VectorClock map[string]uint64
func (vc VectorClock) Tick(node string) VectorClock {
next := vc.Copy()
next[node]++
return next
}
func (vc VectorClock) Merge(other VectorClock) VectorClock {
next := vc.Copy()
for node, value := range other {
if value > next[node] {
next[node] = value
}
}
return next
}
func Compare(a, b VectorClock) string {
aLess := false
bLess := false
nodes := unionKeys(a, b)
for _, node := range nodes {
if a[node] < b[node] {
aLess = true
}
if b[node] < a[node] {
bLess = true
}
}
switch {
case aLess && !bLess:
return "before"
case bLess && !aLess:
return "after"
case !aLess && !bLess:
return "equal"
default:
return "concurrent"
}
}Lamport timestamps let logs from many processes be sorted into an order that never contradicts message causality. That does not make the order a real timeline, but it makes debugging easier because a receive cannot appear before the send that caused it.
Dynamo used vector clocks to track multiple versions of an object. If a new write descends from an older version, the old version can be discarded. If two writes are concurrent, both versions may be returned to the application for reconciliation. The shopping-cart example is canonical: merging by union preserves additions but can make deleted items reappear unless deletion intent is represented explicitly.
Session tokens, dotted version vectors, dependency vectors, and vector-clock variants let replicas delay visibility until causal dependencies are present. This supports read-your-writes and prevents dependent objects from appearing before their prerequisites.
For a replicated key-value store, each stored sibling should carry its vector. A write based on a prior read should merge the client context, increment the coordinator component, and then discard dominated siblings while preserving concurrent siblings.
type VersionedValue struct {
Value []byte
Clock VectorClock
}
func Put(existing []VersionedValue, clientClock VectorClock, writer string, value []byte) []VersionedValue {
newClock := clientClock.Tick(writer)
out := []VersionedValue{{Value: value, Clock: newClock}}
for _, old := range existing {
switch Compare(old.Clock, newClock) {
case "before", "equal":
continue // old version is superseded
case "after":
return existing // stale write; caller should reread and merge
case "concurrent":
out = append(out, old)
}
}
return out
}Plain vector clocks grow with the number of participants that have written a key. Systems cap entries, prune inactive writers, or use dotted version vectors to keep per-object metadata bounded. Pruning can lose causality information, so it should be measured as a correctness trade-off rather than hidden as compression.
(lamport, node) is deterministic but arbitrary for concurrent events. Do not use it to decide which user action “really happened first” when no causal path exists.