Parallel Server Systems with Cancel-on-Completion Redundancy

Research output: Contribution to journalArticlepeer-review


We consider a parallel server system with so-called cancel-on-completion redundancy. There are n servers and multiple job classes j. An arriving class j job consists of dj components placed on a randomly selected subset of servers; the job service is complete as soon as kj components out of dj (with kj ≤ dj) complete their service, at which point the unfinished service of all remaining dj − kj components is canceled. The system is in general non-work-conserving in the sense that the average amount of new workload added to the system by an arriving class j job is not defined a priori—it depends on the system state at the time of arrival. This poses the main challenge for the system analysis. For the system with a fixed number of servers n, our main results include: the stability properties; the property that the stationary distributions of the relative server workloads remain tight uni-formly in the system load. We also consider the mean-field asymptotic regime when n → ∞ while each job class arrival rate per server remains constant. The main question we address here is: under which conditions the steady-state asymptotic independence (SSAI) of server workloads holds and, in particular, when the SSAI for the full range of loads (SSAI-FRL) holds. (Informally, SSAI-FRL means that SSAI holds for any system load less than one.) We obtain sufficient conditions for SSAI and SSAI-FRL. In particular, we prove that SSAI-FRL holds in the important special case when job components of each class j are independent and identically distributed with an increasing-hazard-rate distribution.

Original languageEnglish (US)
Pages (from-to)340-372
Number of pages33
JournalStochastic Systems
Issue number4
StatePublished - Dec 2022


  • asymptotic independence
  • cancel-on-completion
  • load distribution and balancing
  • mean-field limit
  • multicomponent jobs
  • parallel service systems
  • particle systems
  • redundancy
  • replication
  • steady state

ASJC Scopus subject areas

  • Statistics and Probability
  • Modeling and Simulation
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research


Dive into the research topics of 'Parallel Server Systems with Cancel-on-Completion Redundancy'. Together they form a unique fingerprint.

Cite this