The poset
A partial order records only what must happen before what. Independent tasks remain incomparable—and therefore potentially parallel.
An inverse theory of serialization
What does a sequence forget?
Computation is partially ordered. Execution turns that geometry into a timeline. This project measures what a serial trace hides—and how many independent traces it takes to recover the dependencies underneath.
- Exact-uniform sampler
- Open artifacts
- Reproducible seeds
13,800random posets
0.859rank correlation
182,783trace events
0censored runs
01 / The idea
A timeline is not a dependency graph.
A program run chooses one legal order among many. That observed line contains the true constraints, but it also contains accidental order introduced by the scheduler.
The trace
A serial trace is a linear extension of the poset. It preserves every dependency while adding an order between independent tasks.
The hidden geometry
Intersect repeated traces. Accidental order disappears when both orientations are eventually observed; necessary order survives.
Serialization preserves execution order—but not the geometry of necessity.
The same observed sequence may be compatible with a fully parallel antichain, a fully serial chain, and exponentially many dependency structures in between.
02 / Empirical result
Recovery gets slower as systems grow denser.
Across seven problem sizes and four relation densities, the number of exact-uniform traces needed for recovery rises smoothly with both n and p.
n = 20, p = 0.10
40.3
mean traces to recover the true order
n = 20, p = 0.75
244.1
mean traces—roughly six times the sparse case
Longest observed run
1,679
traces, revealing a pronounced rare-event tail
03 / The mechanism
Rare orientations control the hard cases.
For an incomparable pair x, y, both orders are legal. But legal does not mean equally likely. If one orientation appears only rarely, every other ambiguity can vanish while recovery still waits for that one missing observation.
The hardest-pair rarity proxy has Spearman correlation 0.859
with observed recovery time across 6,000 independently diagnosed instances.
ρ = 0.859
04 / Formal core
A compact mathematics of trace recovery.
The experiment rests on exact combinatorial definitions: traces are uniform linear extensions, evidence accumulates by intersection, and recovery is a hitting time.
Agreement order
Rk = ⋂ki=1 <πᵢ
Keep only pairwise order that all observed traces agree on. The sequence shrinks monotonically toward the true poset.
Recovery time
T(P) = min { k ≥ 1 : Rk = P }
The first trace count at which every scheduler-imposed comparability has been removed.
Dimension floor
T(P) ≥ dim(P)
Every realized sample path needs at least as many traces as the smallest possible realizer of the poset.
05 / Experiment
Exact where it matters. Auditable end to end.
The pipeline avoids approximate trace sampling. Dynamic programming counts every continuation, then uses integer conditional weights to sample each linear extension uniformly.
Generate
Draw random height-two posets for seven values of n and four relation densities p.
Sample
Draw independent linear extensions exactly uniformly using downset dynamic programming.
Intersect
Update the agreement order after each trace and record when it first equals the ground truth.
Diagnose
Measure fiber decay, exact small-instance dimension, and hardest-pair orientation rarity.
Reproduce the analysis
Tests, deterministic seeds, raw shards, aggregation code, and the final paper are all in the repository.
$ git clone https://github.com/jonland82/dependency-geometry.git
$ cd dependency-geometry
$ python -m pip install -e .
$ python -m pytest -q
Read the full argument
From hidden parallelism to repeated-trace recovery.
The paper connects work-span analysis, partial-order semantics, quadratic single-trace ambiguity, a minimax inference barrier, and exact finite-sample recovery bounds.