Safety-critical software such as driving perception, flight control and satellite attitude control must finish before hard deadlines. Engineers size the hardware by bounding how long a task can possibly take. Exact worst-case bounds are very pessimistic. A newer line of work replaces them with probabilistic bounds: the task is certified to miss its deadline with probability below, say, $10^{-3}$ or $10^{-9}$. Almost every such analysis quietly assumes that the random parts of the computation are statistically independent. Examples are the branch taken by each conditional, the execution time of each sub-task, and the delay each sub-task suffers from shared memory. In real systems these quantities share common causes. A cluttered camera frame makes every vision branch slow at once, and a saturated memory bus slows every core at once.
This note starts from a result in queueing theory. Delay asymptotics and bounds for multitask parallel jobs proves that when a job forks into parallel tasks whose delays are positively correlated in a strong sense ("associated"), computing the job's completion time as if the tasks were independent gives a safe over-estimate. The same reasoning reverses for sums. Positively correlated quantities added in sequence have a heavier tail than independence predicts, so independence under-estimates the risk. A parallel program, modeled as a graph of sub-tasks, combines both operations: it takes maxima where parallel branches join and sums along each chain. So the independence assumption in current probabilistic analyses is neither uniformly safe nor uniformly pessimistic. Its error has a sign that depends on the shape of the graph. We propose to measure that sign, prove where it flips, and build an analysis that stays safe under common-cause correlation without giving back the savings that motivated probabilistic analysis.
Core Claim
Take a parallel task modeled as a directed acyclic graph (DAG): nodes are sub-tasks and edges mean "must finish before." Let its random node weights be positively associated, as common causes make them. An analysis that convolves node weights along paths assuming independence then under-estimates the tail of each path's length. Taking the maximum over parallel paths assuming independence over-estimates it. The net error therefore turns optimistic (unsafe) as graphs get deeper and narrower, and pessimistic as they get wider and shallower.
The current best probabilistic DAG analysis, Exploiting the Uncertainty of the Longest Paths: Response Time Analysis for Probabilistic DAG Tasks, assumes independent branches. It explicitly lists correlated branches as unsolved. We predict that its 99.9% response-time bound will be violated on deep graphs once correlation is moderate.
Our fix is to condition on an explicit common-cause variable $Z$, such as the input-scene class or the co-runner memory load level. Given $Z$, sums along chains are convolved and maxima at joins are combined in product form. A dependence-free bound covers any chain where conditional independence cannot be justified. The result is a response-time tail bound that is provably safe for associated weights and still tight when correlation is strong.
Why the obvious port is not enough
The obvious move at this intersection is to prove the independence upper bound for parallel DAG branches and plug it into existing analyses. We argue this is nearly empty at the tail levels that certification cares about. For $k$ parallel paths, each with exceedance probability $p_h$, the independence bound is $1-\prod_h(1-p_h)$. The union bound $\sum_h p_h$ needs no assumption at all. When every $p_h$ is small, as it is at $10^{-3}$ or $10^{-9}$ targets, the two agree to first order. Porting the theorem therefore buys almost nothing at joins.
The real effects of dependence lie elsewhere, in two places:
- Along chains. Here independence is unsafe.
- The looseness of both bounds under strong positive correlation. When all paths fail together in one bad scenario of probability $\pi$, the true join tail is near $\pi$, not $k\pi$.
Conditioning on $Z$ addresses both. The second gain comes from saturation: given a bad $Z$, every path is likely to exceed the threshold, so its contribution is capped at the probability of that $Z$ instead of $k$ times it. Concretely, the bound is
$$ \mathbb{P}(R>t)\;\le\;\sum_{z}\pi_z\,\min\Big\{1,\;1-\prod_{h\in\Lambda^*}\big(1-\bar p_h(t\mid z)\big)\Big\}, $$
where:
- $R$ is the response time;
- $\pi_z$ is the probability of common-cause state $z$;
- $\Lambda^*$ is the pruned set of candidate longest paths, using the dominance pruning of Gao et al.;
- $\bar p_h(t\mid z)$ is an upper bound on the probability that path $h$ plus its interference exceeds $t$ given $z$.
For $\bar p_h$ we use exact convolution where nodes are conditionally independent. Elsewhere we use the dependence-free split bound $\mathbb{P}(\sum_i X_i>t)\le\inf_{\sum_i t_i=t}\sum_i\mathbb{P}(X_i>t_i)$, which holds because the sum can only exceed $t$ if some $X_i$ exceeds its share $t_i$. The product inside the minimum is safe even when residual contention correlates paths given $z$, provided that residual dependence is positive association. That is exactly the situation the Wang et al. argument covers.
Research Program
Theory. The theoretical part has three pieces.
- Sign theorem. For series-parallel DAGs with associated node weights, we will state and prove which way independence errs. Chain sums under independence are dominated in tail by the true sums, and join maxima under independence dominate the true maxima. For general DAGs, where paths share nodes, path lengths are increasing functions of the same weights and are therefore themselves associated. That gives the join half directly. The chain half needs a counterexample family showing that independent convolution can be arbitrarily optimistic.
- Safety of the conditioned bound. We will prove the displayed bound is safe whenever weights are associated given $Z$, and characterize when it is tight.
- Positive dependence from contention. We will ask whether contention-induced dependence between sibling branches on shared cores is positive. Wang et al. needed Poisson oversampling to prove association for queue workloads. Real-time schedulers are work-conserving and arrivals are adversarial, which is the tension the research file flags. We treat this piece as the riskiest. We will check it empirically before relying on it, falling back to the union bound at joins if association fails.
Analysis tool. The tool takes as input a DAG with per-node conditional execution-time distributions given $Z$ and branch probabilities given $Z$. It reuses the path pruning of Gao et al. and outputs the bound above. Interference from nodes off the candidate path is handled two ways. One is Graham-style smearing of off-path work across cores, Graham's 1969 bound $R \le L + (W-L)/m$ (with $W$ the total work, $L$ the critical-path length and $m$ the number of cores), as Gao et al. do. The other is the multi-path residue bound of Bounding the Response Time of DAG Tasks Using Long Paths, which subtracts several long paths from the interfering work. Both are evaluated per $z$, so the structural tightening and the probabilistic tightening compose.
Prior work in its roles. Several papers motivate the problem:
- Gao et al. flag correlated branches as open and rely on independent branches. Their truncated inclusion-exclusion step carries no stated safety direction.
- Schedulability of probabilistic mixed-criticality systems gets its "multiplexer gain" from summing independent task demands. That is precisely the sum-type use of independence our sign theorem says is optimistic under common causes.
- On the Use of Probabilistic Worst-Case Execution Time Estimation for Parallel Applications in High Performance Systems has to randomize memory layout to make runs independent enough for extreme-value fitting. That is evidence that dependence is real on multicore hardware.
Other papers supply methods we reuse: Wang et al. for the join-side theorem and the asymptotic picture, Gao et al. for path pruning, and He et al. for residue paths. The multi-path work is deterministic and offers no handle on correlation, so it constrains only the interference term.
Baselines
The naive reference point is the deterministic Graham bound with per-node worst-case execution times. It is always safe and shows how much any probabilistic method saves.
The strongest structural deterministic competitor is the multi-path residue bound of Bounding the Response Time of DAG Tasks Using Long Paths. That paper reports a 13.1% to 16.2% improvement over Graham's predicted response times and a 47.9% average reduction in required cores on Erdős–Rényi DAGs, which are random graphs with a fixed edge probability. It matters because a safe deterministic bound that is already this tight sets the floor any probabilistic method must clear to be worth its assumptions.
The strongest probabilistic competitor is the independent-branch path analysis of Gao et al. It reports 36.33% fewer cores at a 99.9% confidence level, with an average deviation of 1.04% from exact enumeration. That 1.04% is measured against enumeration under its own independence assumption, not against correlated ground truth. We run it on identical graphs, distributions and confidence levels, and feed it the correct marginal of each branch, so it is penalized only for the independence assumption.
We also run a measurement-based extreme-value baseline (MBPTA-CV, the method of the HPC paper). It fits tails to end-to-end samples from the same simulator, with the same sample budget our method uses to estimate conditional distributions.
Two ablations isolate our ingredients:
- Dependence-free union bound. We replace $Z$-conditioning with the dependence-free bound everywhere: union at joins, split bound on chains. This isolates the value of conditioning.
- Conditioning plus independence everywhere. We keep $Z$-conditioning but assume conditional independence everywhere, without the split-bound fallback. This isolates the value of the safety fallback.
Beating Gao et al. means two things together. First, our bound must hold: the true exceedance probability of our 99.9% bound must stay at or below $10^{-3}$ across every correlation level where theirs exceeds it. Second, wherever theirs is safe, our core counts must stay within a small margin of theirs; we set 10% of their savings as the target in advance. Beating the union-bound ablation means strictly fewer cores at equal safety under strong correlation.
Why not just…?
Why not just use the union bound, which is safe under any dependence? This is the most serious threat. At joins it matches the independence bound to first order, so if correlation is weak it will do as well as our method. It falls short in two places. Along chains it still needs a dependence-free sum bound, which is loose. At joins it charges $k$ times the probability of a shared bad scenario, while conditioning charges it once. The union-bound ablation measures this directly across a correlation sweep. If it comes within a few percent of our core counts at all correlation levels, we will report that conditioning is unnecessary and the contribution reduces to the sign theorem and the safety audit of existing analyses.
Why not just fit an extreme-value tail to end-to-end measurements? That avoids modeling dependence altogether. But the HPC study reports about 20% slowdown from the code randomization needed to make samples behave independently. The SAFE study, Estimating Probabilistic Safe WCET Ranges of Real-Time Systems at Design Stages, notes that sampling cannot see interference states never observed. A black-box tail also cannot say which paths dominate, so it cannot drive structural changes such as the edge insertion of Longer Is Shorter: Making Long Paths to Improve the Worst-Case Response Time of DAG Tasks. We include it as a baseline, and its safety under correlated rare scenarios is measured the same way as ours.
Why not just enumerate scenarios? Conditioning on $Z$ is enumeration over a deliberately small common-cause variable, not over branch combinations. Gao et al. report that branch enumeration fails beyond seven conditional structures. Our cost scales with the number of $Z$ states times the path-based cost. We will report runtime as $Z$ grows to find where this stops being cheap.
Why not just use deterministic isolation and the multi-path bound? That is safe and assumption-free. The mixed-criticality study shows deterministic models failing at utilization 0.8 where probabilistic ones held up to 1.4. Our comparison against the He et al. bound reports exactly how many cores the probabilistic route saves once it is made safe.
Proposed Experiments
Synthetic graphs. We use the synthetic probabilistic-DAG generator of Gao et al., varying layers, nodes per layer and the fraction of conditional structures. We also use the Erdős–Rényi generator of He et al. at 50 to 250 nodes, with 5,000 graphs per configuration as in that work.
Into both we inject a common cause. A latent $Z$ with a handful of states shifts branch probabilities and node execution-time distributions jointly, controlled by a single correlation knob $\rho$ from 0 to near 1. Ground truth comes from Monte Carlo with enough samples per graph to estimate a $10^{-3}$ exceedance with tight confidence intervals. The $10^{-9}$ level is evaluated by importance sampling on the bad $Z$ states.
The decisive check is a two-dimensional sweep over $\rho$ and depth-to-width ratio. It reports the true exceedance probability of each method's 99.9% bound. The sign theorem predicts the following pattern for independent-branch analysis:
- deep, narrow graphs: unsafe as $\rho$ grows;
- wide, shallow graphs: safe but loose.
If independent analysis is safe everywhere, the chain half of our claim is wrong in practice and we say so.
Asymptotic check. A second check imports Wang et al.'s scaling design. A single fork-join stage has $k$ branches contending for $m$ shared resources, which can be cores or memory channels in simulation, with $k$ growing as $m^{1/3}$, $m^{2/3}$ and $m^{9/10}$, the same exponents their simulations used. This tests whether contention-induced dependence between branches is positive, which is what makes the join-side product safe. It also tests whether the gap to independence closes for slowly growing $k$, as in their queueing setting.
Hardware testbed. A third check uses a fork-join pipeline built from Mälardalen benchmark kernels on a multicore board with co-running memory traffic. The shared input parameter is varied to create real common-cause correlation. Here the metric is again empirical exceedance of each bound, plus cores required to meet a fixed deadline.
Across all three settings we report cores required, bound tightness against Monte Carlo truth, and analysis runtime.
References
- Delay asymptotics and bounds for multitask parallel jobs
- Exploiting the Uncertainty of the Longest Paths: Response Time Analysis for Probabilistic DAG Tasks
- Bounding the Response Time of DAG Tasks Using Long Paths
- Schedulability of probabilistic mixed-criticality systems
- On the Use of Probabilistic Worst-Case Execution Time Estimation for Parallel Applications in High Performance Systems
- Estimating Probabilistic Safe WCET Ranges of Real-Time Systems at Design Stages
- Longer Is Shorter: Making Long Paths to Improve the Worst-Case Response Time of DAG Tasks