When Independence Stops Being Safe: Correlated Delays in k-of-n Redundant Jobs

Large computing jobs are often split into many pieces that run on different servers at once. Designers usually estimate how long the whole job takes by pretending each piece's delay is independent of the others. For jobs that must wait for every piece, this shortcut is known to be safe. Real delays are positively correlated, because pieces arrive together and pile into the same queues. That correlation pulls the slowest piece closer to the rest, so the independent model overestimates job delay. This was proved by Wang et al. in Delay Asymptotics and Bounds for Multi-Task Parallel Jobs.

Redundant and coded systems behave differently. They send $n$ pieces and finish as soon as any $k$ return. Here the same positive correlation removes the "lucky fast server" that redundancy is paid to find. At the extreme of a single needed piece, the independent model becomes optimistic rather than conservative. This note proposes to locate exactly where the shortcut flips from safe to unsafe as $k$ moves from $n$ down to $1$. It also proposes a cheap correction that tracks the flip using one extra measured number per system, a pairwise correlation. Finally, it tests whether the error changes which redundancy level a designer would choose.

Core Claim

Let $T_1,\dots,T_n$ be the delays of the $n$ pieces of one job, and let $T_{(k)}$ be the time the $k$-th of them finishes. Let $\tilde T_i$ be independent copies with the same individual distributions. Wang et al. proved that queueing delays in fork-join systems are associated, a strong form of positive dependence. They did this with Poisson oversampling, meaning they look at the system at random Poisson-distributed instants rather than only at arrivals.

If association holds, two classical inequalities follow directly:

$$P(T_{(n)} \le t) \ge P(\tilde T_{(n)} \le t), \qquad P(T_{(1)} > t) \ge P(\tilde T_{(1)} > t).$$

The first inequality says the independent model is pessimistic for the slowest piece. The second says it is optimistic for the fastest piece. For intermediate $k$ there is no general ordering.

To get intuition, write $N_t=\sum_i \mathbf{1}\{T_i\le t\}$ for the number of pieces done by time $t$, so that $T_{(k)}\le t$ exactly when $N_t\ge k$. Positive correlation leaves the mean of $N_t$ unchanged but widens its spread. A wider spread helps when $k$ is above the typical count $nF(t)$, where $F$ is the common delay distribution, and hurts when $k$ is below it.

Our claims are threefold. First, the independent model overestimates delay for large $k$ and underestimates it for small $k$, with a crossover near the order statistic whose typical count matches $k$. Second, modeling $N_t$ as a beta-binomial count captures most of the gap at any scale. A beta-binomial is the count distribution that exchangeable correlated indicators produce. Fitting it needs only the marginal $F(t)$ and the pairwise correlation $\rho(t)$ of two pieces' completion indicators. Third, in the redundancy regime where $k$ is well below $n$, the independent model's optimism systematically pushes designers toward too much redundancy. This shifts the minimum of the familiar U-shaped curve of latency against redundancy.

Research Program

Theory. The first task is to extend the Wang et al. association proof from all-must-finish jobs to $(n,k)$ jobs without early cancellation. In this setting every piece runs to completion, so the queue dynamics are those of an ordinary fork-join system. Their argument should carry over, and the two inequalities above then hold exactly.

The harder case is cancel-on-complete, where unfinished pieces are killed once $k$ finish. Cancellation creates departures that couple queues negatively, so association may fail. We will treat this case as an empirical question rather than claim a theorem.

Second, we will ask whether the size of the gap vanishes in the sub-fourth-root regime $k(n)=o(n^{1/4})$, where Wang et al. showed asymptotic independence. If it does, i.i.d. redundancy planning is provably safe there and unsafe beyond it.

Third, we add a shared rack-level slowdown factor, of the kind motivated by Gauri Joshi et al. and Ajay Badita et al.. We will show that this factor gives $\rho(t)$ a floor that does not shrink as the cluster grows. If so, independence fails even for small $k(n)$.

Method. The beta-binomial correction is the deliverable a practitioner would actually use. Both inputs, $F(t)$ and $\rho(t)$, are estimated from traces. Computing it costs about the same as the independent model at any $n$, which avoids the coefficient blow-up of exact order-statistic transforms.

Design consequence. We then rerun the redundancy-level optimization of When Do Redundant Requests Reduce Latency? and Efficient Redundancy Techniques for Latency Reduction in Cloud Systems using the corrected model. Both papers derive the optimal redundancy under independent service times. They also show that light-tailed delays or nonzero cancellation cost make redundancy harmful at high load. We expect correlation to strengthen this "redundancy hurts" region, consistent with the observation in On a unifying product form framework for redundancy models that correlated service times make cancel-on-complete degrade at high load.

Prior work and its role. The prior work plays three roles. The Wang et al. bound supplies the proof technique, and we invert its direction for small $k$. Approximations and Bounds for (n, k) Fork-Join Queues: A Linear Transformation Approach is the closest existing analysis. It writes $T_{(k)}$ exactly as a combination of all-must-finish maxima without assuming independence. However, its coefficients exceed $10^{27}$ at $n=100,k=37$, which constrains it to $n\le 10$. It also never asks about the sign of the independence error. Approximations to Study the Impact of the Service Discipline in Systems with Redundancy shows that mean-field independence fails under redundancy and tracks correlated pairs of servers. It assumes independent replica sizes and single-piece jobs, while we target k-of-n jobs and include shared job size.

Baselines

Naive reference: the independent model. The first reference point is the independent model with true marginals. This is exactly what Efficient Straggler Replication in Large-Scale Parallel Computing and the CoCoI planner CoCoI: Distributed Coded Inference System for Straggler Mitigation use. Every method receives the same simulated marginals, so the comparison isolates dependence alone. Our method beats this baseline if it shrinks the absolute error in mean and 99th-percentile $T_{(k)}$ across the whole range of $k$. It must also get the sign right on both sides of the crossover.

Strongest exact competitor: the linear transformation. The strongest exact method is the linear-transformation approximation of Wang, Li, Shen and Zhou. Its reported accuracy is a relative error "less than 10%" for $n\le 10$, measured on the Forkulator-p simulator with 10,000 job samples per $(n,k)$ pair. We run it on identical $(n,k)$ grids with the same samples. Matching its error at $n\le10$ and staying stable beyond $n=10$ counts as beating it.

Strongest correlation-aware approximation: the pair approximation. The pair approximation of Gast and Van Houdt reports relative errors "below 0.1% for almost all queue length probabilities" against simulations of $10^5$ servers. That figure is for queue lengths in single-piece replication, not k-of-n job delay. We will compare against it only in the overlapping single-needed-piece case with exponential, independent replica sizes.

Ablation: the correlation term. The key ablation sets $\rho(t)=0$ inside the beta-binomial, which recovers the independent model. It also replaces $\rho(t)$ with a single time-averaged constant. Together these show whether the time-varying correlation is what matters.

Why not just…?

Why not just keep using the independent model, since it is a proven upper bound? It is proven only when all pieces must finish. The second inequality above shows it is a lower bound when one piece suffices. The experiments below measure how large this optimism gets for intermediate $k$, which the existing proofs do not cover.

Why not just simulate the cluster and pick the redundancy level empirically? This is a real threat. For a fixed, well-instrumented system, a simulation sweep over redundancy levels will find the best level, and our method cannot beat that on accuracy. Our claim is narrower and different. The correction needs two measured curves instead of a full simulator, it transfers across loads and $(n,k)$ choices, and the theory says when cheap independent planning is safe. We will report the gap between the redundancy level our method picks and the simulation optimum. If that gap shows no advantage in cost or transfer, the method has little practical value beyond explanation.

Why not just use the exact linear transformation or pair approximations? The first becomes numerically unusable at moderate $n$, as its own authors report. The second assumes independent replica sizes and single-piece jobs. Neither captures a shared job size or rack-level slowdowns. The large-$n$ and rack-factor experiments test whether our cheaper model holds where these methods cannot run.

Proposed Experiments

Simulator setup. We will extend a Forkulator-p-style $(n,k)$ simulator and the Wang et al. scaling simulator. Three variants are planned: no cancellation, cancel-on-complete, and cancel with a removal cost. We use exponential service and shifted-exponential service. We also use empirical service times resampled from the Google cluster trace jobs used by Wang, Joshi and Wornell. A tunable rack-level slowdown factor will be added on top.

Grid and metrics. We sweep $n$ up to several hundred, cover $k/n$ from near $0$ to $1$, and include scaling paths $k(n)=n^{1/5},n^{1/3},n^{2/3}$. For each point we record three quantities. The first is the signed error of the independent model in mean and 99th-percentile $T_{(k)}$. The second is the same error after the beta-binomial correction. The third is the redundancy level each model selects, with its latency regret against the simulation optimum.

Decisive checks. There are four. First, the independent model's error should change sign as $k$ falls, with the crossover predicted by the variance argument. Second, without cancellation the error should vanish along $k(n)=o(n^{1/4})$ paths, but not once a rack factor is present. Third, the corrected model should pick redundancy levels with smaller regret than the independent model at high load. Fourth, under cancel-on-complete, we check whether the sign pattern survives. If it does not, that tells us association genuinely fails under cancellation.

Hardware validation. As a small physical check, an edge cluster like CoCoI's shares a single WiFi channel, which is a natural source of correlation. For comparison, CoCoI reports a reduction in average latency of "up to 34.2%" on that testbed. We will measure $\rho(t)$ there and check whether the independent planner's choice of $k$ is optimistic.