Reproducibility as Redundancy: Lineage-Aware Erasure Coding for Dynamic Task Graphs

Python workflow systems such as Parsl and Dask build their task graphs while the program runs. Each call to a parallel function returns a placeholder for its result, and the system records which later tasks depend on it. When a worker dies, its in-memory intermediate results die with it. Today there are two standard recovery options. The first is to recompute the lost result from its recorded ancestry, called its lineage. The second is to have written the result to durable storage beforehand. Recomputation is cheap only when re-running a task reproduces the same bytes and the ancestors are still available. Durable writes are expensive: spooling intermediate data costs Trino 1.5× to 2.7× in failure-free runtime, against 6–15% for logging lineage alone (Write-ahead Lineage). Erasure coding sits between these options. It splits data into $k$ pieces plus a few parity pieces so that any lost piece can be rebuilt, and its repair-traffic cost has been heavily optimized for static file systems. No dynamic task runtime uses it for intermediate state.

This proposal argues that the deciding variable is reproducibility, not data size. A task running in a version-pinned container whose re-execution provably yields identical bytes already has redundancy, because its lineage is a zero-storage code for its output. A task that is not reproducible, such as one using a non-deterministic GPU kernel, an LLM agent step, or a call to an external service, has no such protection. Recomputing it silently produces a different value, and that value then disagrees with whatever downstream tasks and provenance logs already consumed. We propose a runtime layer that does three things. It classifies each node of the dynamically unfolding graph by whether its output can be faithfully reproduced. It erasure-codes only the outputs that cannot be reproduced cheaply. It groups those outputs into coding stripes by when the graph predicts they will stop being needed, so that freeing memory does not force re-encoding.

Core Claim

In a dynamic task graph run inside hermetic containers, the runtime knows three things at the moment a task finishes. It knows whether the task's environment and inputs are pinned, how expensive its ancestry would be to replay, and how many not-yet-run consumers still reference its output. These three facts are enough to decide per object between lineage recovery and erasure coding. The resulting policy should approach lineage-only overhead in failure-free runs. It should also recover non-reproducible state correctly, which lineage-only recovery cannot do, at a fraction of the memory cost of replication.

The decision rule for an object $o$ of size $s_o$ with expected remaining lifetime $\tau_o$ codes it iff

$$p\,\tau_o\, C_{\text{lin}}(o) \;>\; \lambda\,\frac{n-k}{k}\, s_o\, \tau_o + C_{\text{enc}}(s_o),$$

where $p$ is the per-worker failure rate. $C_{\text{lin}}(o)$ is the cost of replaying the ancestry needed to rebuild $o$, taken as infinite if any task on that path is not reproducible. $\lambda$ prices memory over time, $(n-k)/k$ is the parity overhead of an $(n,k)$ code, and $C_{\text{enc}}$ is the encoding cost. The left side is the expected recovery cost over the object's remaining lifetime. The right side is the price of holding parity for that lifetime plus one encoding pass. The rule is deliberately simple. The research contributions lie in estimating its inputs online and in stripe formation.

Research Program

The system builds on Parsl and on Dask with ProxyStore. ProxyStore already separates task-graph metadata from large payloads by passing lightweight references through the scheduler while the data sits in an object store (Dask and ProxyStore; Parsl). That reference layer is where our decisions run. For every object it can see the producing task, the producer's container image digest, and the set of pending consumers.

The first component is a reproducibility classifier. A task counts as replayable if four conditions hold. Its container image is pinned by digest, in the style of the version-pinned registries in SciAgent. All of its inputs are content-hashed objects or replayable outputs. It declares no external side effects. Spot re-execution of a sampled fraction of its instances, on otherwise idle capacity, has produced matching output hashes. Tasks that fail any of these conditions are treated as non-reproducible. The spot check matters because container pinning does not capture GPU floating-point non-determinism or kernel race conditions, a limitation the file names explicitly for container-based reproducibility. We will measure how much sampling is needed before misclassification becomes rare.

The second component is lifetime-aware stripe formation. Erasure codes protect fixed groups of objects. If one object in a group is freed while its stripe-mates live on, the parity must either be recomputed or kept as dead weight. The dynamic graph gives a live estimate of each object's remaining consumers. We therefore bucket objects to be coded by predicted death time and fill stripes within a bucket. Each stripe uses a locally repairable code: small local groups of size $r$, each with its own parity, so that one lost piece can be rebuilt from its local group alone. The code is chosen to meet the redundancy bound $n-k \ge \lceil k/r\rceil + d - 2$ of Gopalan et al., which makes single-worker repair touch $r$ helpers rather than $k$. Here $d$ is the code's minimum distance, the number of piece losses it can detect, so it tolerates $d-1$ lost pieces. Repair transfers are pipelined slice by slice through the helpers, following ECPipe. Each helper combines its slice with the partial result it receives and forwards it, so the replacement worker's network link is not swamped by $r$ simultaneous downloads. ECPipe fixes its helper chain at a static path. Ours is chosen at repair time from whichever workers currently hold the stripe.

The third component makes recovery auditable. Every recovery appends a record to a SciAgent-style append-only log. The record states which mechanism restored the object and the restored object's hash. Downstream consumers and any verifier can then confirm that the recovered value is the one originally consumed.

The work relates to prior systems as follows. Quokka motivates the design: it shows that lineage plus small metadata beats spooling, but it assumes recomputation is always valid and never stores coded intermediate data (Write-ahead Lineage). Regenerating codes, locally repairable codes, and ECPipe supply the coding and repair method, all designed for static block layouts with no notion of object lifetime. SciAgent and OpenHands supply the pinned-container execution model but have no fault tolerance for distributed state. D-Rex (D-Rex) adapts reliability to heterogeneous storage nodes but does not consult a task graph. To our knowledge, none of these uses reproducibility as an input to the protection decision.

Baselines

The naive reference point is unprotected Dask or Parsl execution with ProxyStore. On worker failure, the affected tasks are resubmitted by the framework's default retry. This baseline sets the floor for failure-free overhead. ProxyStore itself reports up to 5.8× speedup in Dask and roughly 50% lower task round-trip time for 100 MB payloads over passing data through the scheduler (Dask and ProxyStore), so we inherit that baseline rather than competing with it.

The strongest existing method for the failure-free cost question is write-ahead lineage in the style of Quokka. Before any output is consumed, only small lineage records are persisted, and recovery replays lost tasks in parallel. It reports 6–15% failure-free overhead and about 2× SparkSQL speed on TPC-H at scale factor 100 (Write-ahead Lineage). Quokka is a SQL engine, so we will reimplement its write-ahead invariant inside the same Parsl/Dask runtime, with the same Redis control store, workers, and failure schedule as our system. Beating it means two things. We must stay within a few percentage points of its failure-free overhead. We must also have strictly lower recovery time on workflows with expensive or non-reproducible tasks, where it either replays long chains or restores wrong values.

The third baseline is 2-way replication of every intermediate object across workers through ProxyStore. It is the simplest robust scheme. A fourth baseline is plain Reed–Solomon coding of all intermediates in arrival order, which isolates what lineage awareness adds over coding everything. Three ablations remove one ingredient each. The first removes the reproducibility classifier and assumes every task is replayable. The second removes lifetime-aware stripes and groups objects in arrival order. The third swaps the locally repairable code for Reed–Solomon with star-topology repair. All variants receive identical hardware, identical failure-injection seeds, and the same tuning budget for code parameters and $\lambda$.

Why not just…?

Why not just recompute everything from lineage? For workflows made entirely of deterministic, short tasks, it would work. We expect our policy to reduce to it there, coding almost nothing, and we will report that case honestly as a tie. It fails in two cases the file makes concrete. The first is long-running scientific steps such as OpenFOAM or RCWA simulations, where replay costs hours. The second is non-reproducible steps such as agent actions and GPU kernels, where replay returns a different answer than the one already consumed downstream. The "classifier off" ablation measures how often that second failure produces silent divergence.

Why not just replicate intermediates twice? This is a real threat when memory is plentiful. Replication has trivial repair logic, no encoding CPU cost, and repair that reads one copy. Its cost is 100% extra memory, against roughly 20–50% for typical local codes, and regenerating codes reduced maintenance traffic by about 25% versus hybrid replication on the PlanetLab trace (Network Coding for Distributed Storage Systems). We will sweep the memory available per worker. If replication matches us on recovery time and throughput at realistic memory pressure, the coding half of the proposal is not worth its complexity. The reproducibility classifier would then survive as a policy for deciding what to replicate.

Why not just turn on erasure coding in the backing object store? Distributed object stores such as DAOS can code data transparently. That store-level coding treats objects as opaque. It codes reproducible outputs that need no protection, and it has no idea when objects will be freed. Our Reed–Solomon arrival-order baseline approximates this option. The lifetime ablation separately measures the parity bytes wasted or re-encoded when stripe-mates die at different times.

Why not just spool to a distributed file system? The cost is already documented: spooling costs Trino 1.5× to 2.7× in failure-free runtime (Write-ahead Lineage). We include spooling only as a reference point for recovery time.

Proposed Experiments

The primary testbed is TaPS (TaPS). It provides eight applications across Dask and Parsl, including Cholesky factorization, Montage, molecular design, and federated learning, plus a built-in failure-injection application. These span a range of graph shapes and payload sizes. To introduce non-reproducible tasks in a controlled way, we will add a mixed workload: TaPS's molecular-design active-learning loop with a GPU surrogate model running non-deterministic kernels, and an LLM-agent step modeled on SciAgent's BRCA1 workflow. In both, the fraction of non-reproducible tasks can be dialed. The file reports no recovery-time or repair-traffic numbers for TaPS failure injection; there is no reported result on Lacuna for TaPS fault recovery, so all baselines will be measured fresh.

The metrics are failure-free makespan overhead relative to the unprotected baseline, peak memory per worker, time to resume progress after a killed worker, and bytes moved during repair. The last is the most important: the fraction of recovered objects whose hash matches the originally consumed value, as checked against the append-only log.

The decisive check is a sweep over the non-reproducible fraction from 0% to 50% of tasks. At 0%, our system should match lineage-only within a few percentage points of overhead, landing inside the 6–15% band Quokka reports for its own engine. As the fraction rises, lineage-only should begin returning mismatched recovered values while ours stays at 100% hash agreement. We should do this while holding less memory than 2-way replication and moving fewer repair bytes than Reed–Solomon star repair. ECPipe's reported 90% repair-time reduction over conventional star repair is the ceiling we expect the pipelined local repair to approach on our small stripes, not to exceed.

Two secondary checks round out the evaluation. One measures how much spot re-execution is needed before the classifier's false "reproducible" rate falls below 1%, and what that sampling costs. The other measures how often lifetime-aware stripes avoid re-encoding compared with arrival-order stripes. A negative result on either would be informative. If spot-checking is too costly, reproducibility must be declared by the user rather than detected. If lifetimes are too unpredictable to bucket, the coding layer collapses into per-object replication.