Coded distributed computing protects a computation against slow machines, called stragglers, by adding algebraic redundancy. A matrix product is split into $k$ pieces and encoded into $n>k$ pieces, one per worker, and the answer can be decoded from whichever $k$ workers finish first. The results in this area are strong but almost all come from a single job on an otherwise idle cluster. Real clusters serve a stream of such jobs. Each worker then holds a queue of coded pieces from many jobs, and the $n-k$ pieces nobody needs still take up worker time. Queueing theory has studied this issue for plain replication, where every job is copied $d$ times and the extra copies are cancelled once one finishes. The central finding there is that the order in which a server works through its queue decides whether the redundancy is nearly free or cuts the cluster's usable throughput by a factor of $d$.
This note proposes carrying that finding over to coded computing. The worker-side policy we propose is Least-Slack-First. Each job's "slack" is the number of its coded pieces still outstanding minus the number of results it still needs, and a worker always runs a piece from the job with the smallest slack, choosing at random among ties. For plain replication, slack equals $d-1$ and the rule reduces exactly to Least-Redundant-First, a policy already proved to support the largest possible arrival rate. For coded jobs, slack falls as results arrive. Worker effort therefore goes to jobs about to decode, and pieces of already-decoded jobs are cancelled before anyone starts them. We will prove where this keeps the full stability region and measure what it buys in tail latency over first-come-first-served queues, processor sharing, lower code rates, and replication.
Core Claim
Model a stream of $(n,k)$ coded jobs arriving at rate $\lambda$ to $n$ workers. Each coded piece carries $1/k$ of the job's work, and a job's piece $i$ can run only on worker $i$, because worker $i$ stores the $i$-th encoded data block. That placement constraint is what makes this a genuine redundancy queueing problem. A central dispatcher cannot reassign pieces to whichever worker is free, so the system is exactly the server–job compatibility graph studied in On the Stability of Redundancy Models. That paper shows that replicas with identical work are the dangerous case. Under processor sharing they shrink the stable load from $\rho<1$ to $\rho<1/d$, while random order of service keeps $\rho<1$. Coded pieces from one job are identical in size by construction, so they fall in the dangerous "identical" case, not the benign independent case.
We make three claims. The first is that under processor sharing with homogeneous workers, all $n$ pieces of a job advance in lockstep and nearly all of them are processed before cancellation. The stability region should therefore collapse to roughly
$$\rho < \frac{k}{n},$$
where $\rho = \lambda \, \mathbb{E}[S]/n$ is the load measured in uncoded work $S$. This is the coded analogue of the $1/d$ result; it follows by setting per-job consumed work to $n/k$ times the useful work. Server-speed variability should widen this region somewhat, and we will quantify by how much.
The second claim is that Least-Slack-First with random tie-breaking is stable for all $\rho<1$, for any correlation between pieces. This would generalize the maximal-stability proof for LRF-ROS in Efficient scheduling in redundancy systems with general service times.
The third claim is that at high load the policy reduces 99th-percentile job latency relative to first-come-first-served coded queues. We also expect it to close most of the gap that a skeptic would try to close by simply lowering the code rate as load rises.
Relation to Prior Work
The work that motivates this proposal is the redundancy-queueing line. When Do Redundant Requests Reduce Latency ? shows that the shape of the service-time distribution and the cost of cancellation decide whether redundancy helps. It shows in particular that non-zero removal cost hurts near capacity. On the Stability of Redundancy Models supplies the identical-versus-independent distinction and the collapse under processor sharing. Efficient scheduling in redundancy systems with general service times introduces two-level class/within-class policies and reports that Least-Redundant-First and Most-Redundant-First beat redundancy-oblivious first-come-first-served by 1.5x to 2.5x in mean response time in high-variability settings. All three study whole-job copies that need one completion. None has a job whose need shrinks as partial results arrive, and that shrinking need is the feature our slack definition captures.
The work that supplies our analysis method is Approximations to Study the Impact of the Service Discipline in Systems with Redundancy. It builds ODE pair approximations that treat servers as nodes and shared jobs as edges, and it reports relative error below 0.1% against simulations with $10^5$ servers. We will extend its state to track how many results each job still needs.
The boundary papers constrain our novelty claim. The MDS Queue: Analysing the Latency Performance of Erasure Codes already models $(n,k)$ jobs in a queue, but it assumes exponential service, storage reads, and first-come-first-served-style bounding policies. It does not compare disciplines or characterize the processor-sharing collapse. Coded Sequential Matrix Multiplication For Straggler Mitigation codes across a stream of jobs, but in synchronous rounds with no arrival process and no stability analysis. Coded Computation Over Heterogeneous Clusters and Slack squeeze coded computing for adaptive straggler mitigation size each worker's share of a single job, the first from known speed distributions and the second from LSTM speed prediction. Both are one-shot decisions that ignore queues. They are complementary, since load sizing decides how much each worker gets and our policy decides in what order workers serve jobs, so we treat them as baselines to combine with rather than as competitors. Speeding Up Distributed Machine Learning Using Codes supplies the coded matrix-multiplication workload itself.
Research Program
The theory has three parts. First, we will derive fluid limits for $(n,k)$ coded streams under processor sharing, first-come-first-served, random order, and Least-Slack-First. We start from the nested and $d$-choice topologies where the redundancy proofs already work, then move to the cyclic placement used in coded elastic computing. We will use two straggler models: the "identical work, slow server" model and independent per-piece runtimes. Second, we will prove or refute maximal stability of Least-Slack-First with random tie-breaking. The expected route is the one used for LRF-ROS: jobs with low slack are served as if they had few choices, and random tie-breaking prevents the head-of-line synchronization that makes first-come-first-served fragile with identical copies. Third, we will extend the pair approximation to predict latency distributions for large $n$ under Weibull, hyperexponential, and shifted-exponential service. These are the distributions used by the redundancy and heterogeneous-coding papers.
On the systems side, we will build a coded matrix-vector and gradient service. Encoded blocks are pinned to workers. Jobs arrive as Poisson or trace-driven streams, and each worker runs a pluggable queue discipline. The master decodes after $k$ results and broadcasts cancellation. The cancellation rule is itself a design choice: drop queued pieces only, or also abort running ones. We will measure both, because abort latency is exactly the removal cost that Shah et al. show matters near capacity. Decoding time at the master will be measured, not assumed away.
Baselines
The naive reference is uncoded execution with first-come-first-served queues. Each job is split into $n$ equal uncoded pieces and must wait for all of them. The literature quantifies this gap for single jobs: Lee et al. report a 40% reduction in average runtime and 60% in 95th-percentile latency from MDS coding on EC2 (Speeding Up Distributed Machine Learning Using Codes). We will check whether that advantage survives under queueing.
The strongest coded baseline is the MDS queue under first-come-first-served with cancellation of queued pieces (The MDS Queue: Analysing the Latency Performance of Erasure Codes). This is the default any practitioner would deploy. No reported numeric result was found on Lacuna for its latency, since its bounds are given as analytic curves, so we will reimplement it on identical jobs, code rates, and hardware. Processor-sharing coded queues are run alongside it to test the collapse prediction directly.
The strongest scheduling baseline is LRF-ROS applied to plain replication (Efficient scheduling in redundancy systems with general service times), with 1.5x to 2.5x mean-response-time gains over first-come-first-served reported there. Fairness requires the same redundancy budget. We therefore compare $(n,k)$ coding against replication with total work $n/k$ times the job, on the same workers and arrival traces. Each policy gets the same tuning grid over code rate or replication factor.
We will also run a load-sizing baseline, HCMM-style allocation from Coded Computation Over Heterogeneous Clusters, which reports 42% simulated and 36% EC2 speedups over uniform coded allocation. HCMM is run both with first-come-first-served and combined with Least-Slack-First.
Two ablations isolate the key ingredient. The first uses slack priority with first-come-first-served tie-breaking, to separate the value of slack from the value of randomization. The second prioritizes by remaining-results only, ignoring outstanding pieces, to check that slack rather than mere closeness to decoding is what matters. Beating the baselines means two things. The measured stable load must exceed first-come-first-served and processor sharing by a margin consistent with the fluid limits. And at loads of 0.8 and above, 99th-percentile latency must beat the best-tuned baseline across all three service distributions, not just the heavy-tailed one.
Why not just…?
Why not just lower the code rate as load rises? This is the real threat. If the $k/n$ collapse is the only problem, a controller that shrinks $n$ toward $k$ under high load might recover most of the throughput. It would do so at the cost of straggler protection exactly when queues are long, and long queues are when a slow worker hurts most. We will pit an oracle-tuned, load-dependent code rate against Least-Slack-First at fixed rate. If the adaptive rate matches Least-Slack-First on 99th-percentile latency across distributions, we will report that the scheduling contribution is only a stability result and reframe the work around combining the two.
Why not just replicate and use LRF-ROS, which is already proved maximally stable? Replication must pay integer multiples of whole-job work, and coding pays the fractional $n/k$. At equal redundancy budget, coding tolerates more stragglers. The equal-budget comparison above settles whether that advantage survives queueing. Least-Slack-First is also not a separate mechanism from LRF but its generalization, so if replication wins, the policy still applies.
Why not just predict worker speeds and size loads, as S2C2 does? S2C2 reports 19% to 39% latency cuts but mis-predicts speeds up to 18% of the time (Slack squeeze coded computing for adaptive straggler mitigation), and it decides per job without seeing other jobs' queued pieces. Load sizing and queue order act on different quantities, so our experiments run them together. If sizing alone matches the combination, queue order does not matter in practice.
Why not just use first-come-first-served, which Gast and Van Houdt found beats processor sharing and last-come-first-served? Their comparison excludes priority policies, and the identical-copy results of Anton et al. show first-come-first-served stability degrading to $\rho<\ell/K$. Since coded pieces are identical by construction, we expect the same weakness. The stability-boundary experiment measures it directly.
Proposed Experiments
Simulation comes first. We will use 10 to $10^4$ workers with $(n,k)$ ranging from $(10,7)$ to $(20,16)$, capping $n$ near 20 because floating-point Vandermonde decoding degrades beyond that. Service times follow Weibull, hyperexponential, and shifted-exponential laws, under both identical-work and independent straggler models. For each policy, we sweep load until the queue diverges, which locates the empirical stability boundary. That boundary is compared against $k/n$ for processor sharing and against 1 for Least-Slack-First. The pair approximation is validated against these simulations.
The testbed experiments cover three workloads. The first is coded matrix multiplication at the $5750 \times 5750$ scale of Lee et al. on 25 cloud workers. The second is coded logistic-regression gradients on the Amazon Employee Access and UCI Gisette datasets used by Ye and Abbe and by S2C2. The third is the MNIST stream of 10,000 matrix multiplications from Krishnan et al., which lets us include their interleaved codes as a streaming baseline. In each workload, jobs arrive as a Poisson stream rather than one at a time. We report mean latency, 99th-percentile latency, sustained throughput, wasted worker-seconds on cancelled pieces, and master decoding time.
The decisive check is the pair of stability boundaries. If processor sharing on real coded jobs does not collapse toward $k/n$, the premise that coded pieces behave like identical replicas is wrong. If Least-Slack-First does not hold near $\rho=1$ where first-come-first-served diverges, the policy offers nothing over existing practice.
References
- On the Stability of Redundancy Models
- Efficient scheduling in redundancy systems with general service times
- When do redundant requests reduce latency ?
- Approximations to Study the Impact of the Service Discipline in Systems with Redundancy
- The MDS Queue: Analysing the Latency Performance of Erasure Codes
- Coded Sequential Matrix Multiplication For Straggler Mitigation
- Coded Computation Over Heterogeneous Clusters
- Slack squeeze coded computing for adaptive straggler mitigation
- Speeding up distributed machine learning using codes