Parallel Server Systems with Cancel-on-Completion Redundancy

DOI10.1287/STSY.2022.0094MaRDI QIDQ5870770zbMATH OpenOpenAlexFDO

Authors Alexander L. Stolyar

Publication date 23 January 2023

Published in Stochastic Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.14143

zbMATH Keywords

asymptotic independencecancel-on-completionload distribution and balancingmean-field limitmulticomponent jobsparallel service systemsparticle systemsredundancyreplicationsteady state

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22)

Abstract: 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 $d_j$ components, placed on a randomly selected subset of servers; the job service is complete as soon as $k_j$ components out of $d_j$ (with $k_{j}le{d}_j$) complete their service, at which point the unfinished service of all remaining $d_j-k_j$ 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, uniformly in the system load. We also consider the mean-field asymptotic regime when $noinfty$ 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 $1$.) 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 i.i.d. with an increasing-hazard-rate distribution.

Recommendations

• Large-scale parallel server system with multi-component jobs
• On the stability of a class of non-monotonic systems of parallel queues
• Stability of parallel server systems
• Uniform stability of some large-scale parallel server networks
• Delay asymptotics and bounds for multitask parallel jobs

Cites work

• Asymptotic independence of queues under randomized load balancing
• Ergodicity of stochastic processes describing the operation of open queueing networks
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 1190409 (Why is no real title available?)
• Large-scale join-idle-queue system with general service times
• Large-scale parallel server system with multi-component jobs
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Pull-based load distribution in large-scale heterogeneous service systems
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Redundancy-\(\mathbf{d}\): the power of \(\mathbf{d}\) choices for redundancy
• Stability of queueing networks

Cited in

(5)

• Large-scale parallel server system with multi-component jobs
• Redundancy scheduling with scaled Bernoulli service requirements
• Delay asymptotics and bounds for multitask parallel jobs
• scientific article; zbMATH DE number 1863332 (Why is no real title available?)
• The parallel client--server paradigm

This page was built for publication: Parallel Server Systems with Cancel-on-Completion Redundancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5870770)