Experiments and implementations · Intermediate

Assign logical clocks to an event DAG

Compute ancestor sets and Lamport labels in a three-process model, checking causal direction, a converse counterexample and wall-clock reversal.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Supply event relations explicitly
  2. Compute after dependencies are known
  3. Check the forward property and its failed converse
  4. Recompute every displayed label
  5. Check what process names and input order actually control
  6. Solve the additional-local-event exercise
  7. Ask Logeia about this articleCheck your understanding

Supply event relations explicitly

Assign Lamport labels to seven events across A, B and C and check that causal predecessors have smaller labels. Read the logical-clock guide first. This is a deterministic DAG model, not a program inferring causality from network observations. Each input includes identity, process, known dependencies and an illustrative wall-clock value. Earlier list position alone does not make an event a causal ancestor.

A has a,c; B has b,d,e; C has f,g. Message edges are c to d and e to g, while each process contributes local order. Thus a reaches g through c,d,e, and b reaches d, but b does not reach c. Draw these edges before execution. Adding edges afterward to fit numeric labels would erase the very counterexample being studied. The known input relations, not the printed labels, define the model's causality.

Compute after dependencies are known

Save clocks.py and run it with Python 3.12 or later. Inputs are ordered so every dependency is already available; an assertion enforces that condition. Each label is one greater than the maximum parent label, or one when there are no parents. At a receive, parents include the previous local event and message send, matching the logical receive update rule.

Reordering input to reference an unknown send fails. A real receiver gets a timestamp in a message and need not retain the sender's entire graph. This model holds the graph centrally to inspect the property, a deliberate difference from deployment. Cyclic dependencies are outside its valid event-history input and are not solved by the update loop. Reproduce the input assumptions alongside the procedure instead of interpreting one centralized calculation as a complete distributed clock service.

Check the forward property and its failed converse

For each event, ancestors union direct parents and their ancestors. Assert clock[a]<clock[b] for every ancestor-descendant pair, including long paths such as a to g. Then assert b's label one is smaller than c's two while b is not an ancestor of c. Numeric order therefore does not establish causal order. Equal labels for a and b also do not establish physical simultaneity.

Illustrative wall-clock labels put c at 101 and its receive d at ninety, while logical labels two and three preserve their causal edge. These wall values are supplied examples, not measured clock-synchronization error. Before inferring causes from displayed timestamps, identify actual send/receive edges. Separate assertions check logical order and wall-clock reversal rather than treating one passing condition as proof of every timing property.

python
events=[
 ('a','A',[],100),('b','B',[],95),('c','A',['a'],101),
 ('d','B',['b','c'],90),('e','B',['d'],91),
 ('f','C',[],80),('g','C',['f','e'],81)]
clock={};ancestors={};last={};wall={}
for name,process,dependencies,time in events:
    required=list(dependencies)
    if process in last and last[process] not in required:required.append(last[process])
    assert all(dep in clock for dep in required)
    clock[name]=max([clock[dep] for dep in required]+[0])+1
    ancestors[name]=set(required)
    for dep in required:ancestors[name]|=ancestors[dep]
    wall[name]=time;last[process]=name
assert all(clock[a]<clock[b] for b in ancestors for a in ancestors[b])
assert clock['c']<clock['d'] and wall['c']>wall['d']
assert clock['a']<clock['e'] and 'a' in ancestors['e']
assert clock['b']<clock['c'] and 'b' not in ancestors['c']
print('logical',clock,'noncausal pair b,c','wall order c,d reversed')

Recompute every displayed label

A passing run prints a=1, b=1, c=2, d=3, e=4, f=1 and g=5. For d, take max of B's previous one and incoming two, then increment. For g, use C's one and incoming four. Recompute from parents instead of memorizing the sequence. The published input has executed successfully. It measures neither elapsed duration nor network delay nor actual host offset, and process names are strings rather than three OS processes.

A total-order extension can compare label and stable process identity, but input-list order is not a measured physical total order. Sorting b and c does not create an edge. Scalar labels may lack information required to detect concurrency, motivating richer metadata such as vector clocks under additional costs. Explain the missing information using this counterexample before adding another mechanism. That keeps the model's modest guarantee precise and useful.

Check what process names and input order actually control

Renaming processes while preserving local and message edges keeps the forward clock property. A display using names to break ties can reorder concurrent events, which changes a convention rather than causality. State which ordering is being compared so a changed sorted view is not mistaken for a broken send-receive relation.

Swapping independent a and b in the input list while keeping dependencies available may leave their local clocks unchanged. That follow-up checks that the code is not using one global list index as a distributed timestamp. Moving d before its unknown send c instead violates the model's input precondition and should be rejected. Input-processing order and the world's causal relation are not the same object. A version supporting unresolved references would need pending dependencies and cycle handling, neither of which this loop claims to implement. Likewise, its ancestor sets are supplied-and-derived diagnostic metadata, not transmitted vector-clock state. Keep that implementation distinction when comparing richer causal tracking. The example is complete when a reader can predict both an accepted reordering and an invalid one from the graph rules, rather than relying only on the final increasing sequence of printed numbers.

A rejected unknown dependency is an input-contract result, not a counterexample to the clock condition. Record valid reorderings and invalid references separately so successful numeric output is not the only considered test outcome.

Solve the additional-local-event exercise

Insert an independent local event before C's f. It gets one, f becomes two and g remains max(2,4)+1=five. A new causal relation can therefore exist without changing g's label; numbers do not reconstruct every edge. Advancing B's outgoing e to five would instead make g six. Separate adding an edge from changing which parent controls the maximum.

May b be added as a dependency of c merely because b's number is smaller? No: it needs a real local-order or message relation. Numeric coincidence is not a causal observation. No files or servers are created by the model. The learning outcome maps event, direct edge, ancestor, logical number and wall-clock label to the exact assertion each supports.

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