Scheduling and Stability in Redundant Queueing Systems

13 concepts7 papers1 proposal

Imagine you are waiting for a web page to load. If the server handling your request encounters a transient hiccup (a "straggler"), your request hangs. To combat this, what if you sent the exact same request to three different servers simultaneously, and simply took the result from whichever one finished first?

This strategy, known as job redundancy, is widely used in large-scale distributed systems to mitigate tail latency. At first glance, it seems like a free lunch. However, duplicating tasks introduces a fundamental tradeoff: while it can dramatically reduce latency for an individual user, it multiplies the total workload imposed on the infrastructure. If every user replicates their tasks, the servers can easily become overwhelmed, causing queues to explode.

Recent research focuses on understanding this delicate balance, mapping out exactly when redundancy transitions from a performance booster to a system bottleneck, and designing scheduling policies to keep these systems stable.

When Does Redundancy Help?

To understand why redundancy works, we must look at the variability of server capacities and job execution times. If server performance is perfectly stable and predictable, creating replicas is purely wasteful. As noted by Xu et al. in Online Job Scheduling with Redundancy and Opportunistic Checkpointing: A Speedup-Function-Based Analysis, the effectiveness of job redundancy is deeply tied to the variability of machine service capacity; when capacities are stable, introducing redundancy merely squanders resources.

Furthermore, the mathematical shape of the job service time distribution dictates whether redundancy is viable. In When Do Redundant Requests Reduce Latency ?, Shah et al. demonstrated that redundancy is a winning strategy when service times are "heavy-tailed"—meaning there is a non-trivial probability that a job will take an exceptionally long time to complete. In these scenarios, the chance of hitting a straggler is high, and a backup copy can dramatically lower latency. Conversely, for "light-tailed" distributions (where service times are highly predictable), or when canceling redundant tasks isn't instantaneous, redundancy acts as a performance killer, driving the system toward instability as request arrival rates increase.

The Hidden Danger of Identical Replicas

A critical nuance in modeling redundant systems is how the execution times of job copies relate to one another. Are the copies independent (e.g., a copy on Server B might finish much faster than the copy on Server A due to network jitter), or are they identical (e.g., the job inherently requires the exact same amount of computation on any server)?

In On the Stability of Redundancy Models, Anton et al. demonstrated that this distinction dictates whether a system remains stable. When job copies have independent and identically distributed (i.i.d.) service times, redundancy generally preserves the system's stable operating region. However, if the replicas are identical, multiple servers may end up processing the exact same task concurrently, leading to massive resource waste.

The authors showed that under a Processor Sharing (PS) scheduling discipline, identical redundancy can shrink the system's stability region to a fraction of its original capacity—inversely proportional to the number of redundant copies sent. This represents a worst-case scenario where the inefficiency of processing identical tasks simultaneously completely outweighs the benefits of parallel execution.

How Scheduling Disciplines Mitigate Waste

Because redundant copies can easily clog a cluster, the choice of server-level scheduling policy is paramount. Traditional scheduling policies are often "redundancy-oblivious," treating every task in the queue uniformly regardless of whether its clones are already being serviced elsewhere.

However, even among traditional policies, some handle redundancy much better than others. In Approximations to Study the Impact of the Service Discipline in Systems with Redundancy, Gast et al. analyzed how different server scheduling policies affect queue lengths. They discovered that First-Come-First-Served (FCFS) scheduling significantly outperforms alternatives like Last-Come-First-Served (LCFS) or Processor Sharing under high loads.

The intuition behind this is elegant: FCFS naturally prioritizes older jobs. Because an older job has spent more time in the system, it is highly likely that one of its replicas on another server is close to finishing (or has already finished). By prioritizing older jobs, FCFS maximizes the likelihood of early replica cancellation, clearing system resources faster and resulting in shorter average queue lengths.

Designing Redundancy-Aware Policies

To truly optimize these systems, researchers have moved toward "redundancy-aware" scheduling. Instead of treating all jobs uniformly, these policies dynamically adjust their behavior based on how heavily replicated a job is.

In Efficient scheduling in redundancy systems with general service times, Anton et al. proposed a two-level scheduling framework that explicitly tracks a job's "degree of redundancy"—the number of copies of a job currently in the system or being processed. The first level of this framework prioritizes job classes based on their redundancy degree, while the second level manages jobs within a class at each individual server using standard disciplines like FCFS.

The authors demonstrated that when service times are highly variable or copies are identical, traditional redundancy-oblivious policies can result in 1.5 to 2.5 times more jobs clogging the system compared to these optimized, redundancy-aware approaches.

Expanding Stability via Heterogeneity and Pooling

While redundancy poses severe stability risks in homogeneous environments, it can be leveraged strategically to expand a system's capabilities when servers are heterogeneous.

In Improving the Performance of Heterogeneous Data Centers through Redundancy, Anton et al. showed that when server capacities vary widely across a data center, dispatching redundant copies can actually expand the stable operating region compared to traditional single-copy job dispatching. This allows the system to handle higher overall arrival rates before becoming unstable, because redundancy naturally funnels work toward faster, underutilized resources.

Finally, implementing redundancy across shared infrastructure introduces complex cooperative dynamics. As explored by Mete et al. in Partial Server Pooling in Redundancy Systems, the exact mechanism used to manage redundancy—such as whether a replica is canceled immediately when a clone starts processing versus when it completes—fundamentally alters how independent service providers should share capacity. While full resource pooling is ideal for some redundancy models, others require a more nuanced "partial sharing" approach to prevent providers from exploiting the system and to incentivize stable, mutual cooperation.

Key Foundational Work

Online Job Scheduling with Redundancy and Opportunistic Checkpointing: A Speedup-Function-Based Analysis (2019) — contributed 2 concept elements to this direction.
Partial Server Pooling in Redundancy Systems (2019) — contributed 1 concept elements to this direction.
When Do Redundant Requests Reduce Latency ? (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_redundancy_aware_scheduling_18455c73,
  title = {redundancy-aware scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/redundancy-aware-scheduling/rdr_18455c73c97149b3bf2fea00e48e168e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_redundancy_aware_scheduling_18455c73_v1,
  title = {redundancy-aware scheduling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/redundancy-aware-scheduling/rdr_18455c73c97149b3bf2fea00e48e168e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake