Study guides · Intermediate

Trace logical clocks and causality

Assign Lamport labels to a three-process history and distinguish causal order, the failed converse, tie-breaking and elapsed time.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Track causal order rather than elapsed seconds
  2. Specify local increments and receive updates
  3. Assign labels to a three-process history
  4. Extend ties without inventing causality
  5. Do not use logical labels as elapsed time or a concurrency oracle
  6. Check the property in an explicit DAG model
  7. Separate repeated receives from repeated business effects
  8. Solve the receive and converse exercises
  9. Ask Logeia about this articleCheck your understanding

Track causal order rather than elapsed seconds

Order intake A sends inventory work to B, which sends a result toward notification C. Wall-clock labels can contradict this chain when host clocks differ. Lamport clocks assign larger logical numbers along local order and message delivery. Read partial failure and message histories first. These numbers are not elapsed-time measurements; they label events consistently with causality.

Happens-before follows local process order, a message's send-before-receive relation, and transitive chains of those edges. Events with no path in either direction are concurrent in this relation. That does not assert physically simultaneous execution; it means the recorded local and message relations do not order them. Printed log order is therefore not the definition of causality. Construct the event graph first so a timestamp or output position cannot silently introduce an unsupported causal edge.

Specify local increments and receive updates

Start each process at zero. Increment before a local event or send and attach that value to a message. On receiving message value m with local value c, assign max(c,m)+1. The receive then has a larger label than its send. Keep initial value and increment convention consistent between prose and code. Different conventions can produce different numbers while preserving the required ordering property, so compare rules rather than treating every numeric difference as an error.

Concurrent threads updating one clock need proper synchronization. A sequential dictionary model does not prove that implementation. Restarting a process at zero can also reuse old labels; durable identity may need process generation and retained state. The update rule does not itself deduplicate messages or make every process share the same current number. State which operation uses a logical label and which properties require additional identity, persistence or coordination.

Assign labels to a three-process history

Let A's event a have label one and B's independent b also one. A's next send c gets two. B receives c at d, updating max(1,2)+1 to three. B's following send e gets four. C performs independent f at one, then receives e at g with max(1,4)+1, giving five. The message edges are c to d and e to g. Their local continuations show a causally precedes g, with one less than five.

Events b and c have no causal path in either direction in this history, despite labels one and two. This refutes the converse: causality implies increasing Lamport labels, but increasing labels do not establish causality. Wall-clock labels of 101 for c and ninety for d do not change their send-receive relation. Compare both columns while keeping graph edges authoritative for the causal question. A numeric ordering can be useful without proving an underlying dependency.

EventProcess and relationLogical label
aLocal A1
bLocal B1
cSend from A2
dB receives c3
eSend from B4
fIndependent local C1
gC receives e5

Extend ties without inventing causality

Events a, b and f all have label one. A stable ordering A<B<C permits lexicographic comparison of (logical value, process ID), assuming unique local event labels within a process generation. This extends causal order by adding an arbitrary order between concurrent events. Choosing A before B by identifier does not make A the cause of B. The ordering can support a display or algorithm while remaining a convention for previously unordered pairs.

Constructing sortable labels does not mean every node already knows the same complete event set. A smaller-labeled event might arrive later. Deciding when output is final requires additional information. Lamport clocks alone do not complete consensus or leader election. Nor does serving every smaller label first automatically satisfy deadlines or fairness. Return to the rules of the algorithm using the labels, rather than attributing every desired ordering property to the clock update rule.

Do not use logical labels as elapsed time or a concurrency oracle

A label increase from two to five does not mean three milliseconds elapsed. A busy process can advance many times without communication. Timeouts need an elapsed-time clock, and equal logical labels do not prove simultaneous physical events. Compare this with deadline propagation: its monotonic clock and this logical clock can both increase, but they measure different things.

Different Lamport labels also do not rule out concurrent updates. A concurrency query may need additional causal metadata such as vector clocks, with corresponding storage and membership costs. The conclusion is to choose information matching the required query, not that Lamport clocks are useless. For deduplication alone, stable operation identity and processed-result storage may be the main mechanism. Specify what comparison supports what decision rather than expecting one clock name to supply duration, concurrency, uniqueness and agreement together.

Check the property in an explicit DAG model

The companion experiment supplies local order and send-receive relations as a directed acyclic graph, processed after dependencies are known. It computes ancestor sets and asserts increasing labels for causal edges and transitive ancestors. It also checks the b,c converse counterexample and reversed wall-clock order for c,d. This is a specified event-history model, not observation of real network messages or thread races.

An event appearing earlier in the input list does not automatically become a causal predecessor. Independent progress must remain possible. Assigning one global list index would produce ordered labels but change the experiment away from independently updated local clocks. Identify the relations supplied as known input. Unknown send references or cyclic dependencies in extensions require rejection or a different processing procedure. The graph, its assumptions and its assertions define the verified scope, rather than a generic claim that distributed time has been synchronized.

Separate repeated receives from repeated business effects

A duplicated message can create two receive events, each advancing the local clock. A larger label does not establish that a new business request occurred. Deduplication needs stable message or operation identity and its own effect boundary. Conversely, if a message carries no sender label, assigning only a receiver label does not supply the missing information needed to inspect that send-receive relation.

Collected logs also arrive in an order different from original events because of buffering and retry. Correlation identity, process generation, local sequence and send-receive association can help reconstruct causal edges. Do not expect one scalar label to encode every relationship a diagnostic query might ask. Choose metadata from the actual question. This is another instance of the failed converse: a convenient sorted log view is a presentation order, not proof that each earlier printed event caused every later event. Preserve the graph evidence when investigating a distributed failure.

Use the convenient view while retaining the evidence needed for causal claims.

Solve the receive and converse exercises

A process at seven receiving message four assigns max(7,4)+1=eight, never moving back to five. A process at two receiving nine assigns ten. Merely incrementing local two to three would violate send-before-receive labeling. Explain the receive rule from that required edge. Neither calculation reveals a duration in milliseconds.

Can b at one be concluded to cause c at two? No; their graph has no path in either direction. A tie-breaker can add order without adding causality. Explain update rule, causal edges, conventional total order and physical time separately. When proceeding to distributed transactions, preserve the same discipline: sorting timestamps does not itself atomically commit several resources. The labels support reasoning but do not replace the coordination protocol.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 16

Choose a learning path