2021/05/28 by Alexander Stolyar, Stolyar, Alexander
Business, Management and Accounting · Computer Science · #60K25 #90B15 #Advanced Queuing Theory Analysis #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Mathematics #Networking and Internet Architecture (cs.NI) #Probability (math.PR) #Real-Time Systems Scheduling
paper · pdf · doi:10.48550/arxiv.2105.14143
openalex publication_date 2021/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, uniformly 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 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.