Parallel server systems with cancel-on-completion redundancy

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$ complete their service, at which point the service of all remaining $d_j-k_j$ components is canceled. The system is in general non-work-conserving -- the average amount of new workload added to the system by an arriving class $j$ job depends on the system state. This poses the main challenge for the system analysis. The results of this paper concern both the system with fixed number of servers $n$ and the mean-field asymptotic regime when $n\to\infty$ while each job class arrival rate per server remains constant. The main question we address for the asymptotic regime is whether the steady-state asymptotic independence of server workloads holds. We prove that this property does hold under certain conditions, including the important special case when job components of each class $j$ are i.i.d. with an increasing-hazard-rate distribution.