2021/05/28 by Youri Raaijmakers, Raaijmakers, Youri, Sem Borst +3
Business, Management and Accounting · Computer Science · Engineering · #Advanced Queuing Theory Analysis #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #FOS: Mathematics #Performance (cs.PF) #Probability (math.PR) #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2105.13738
openalex publication_date 2021/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the tail asymptotics of the response time distribution for the cancel-on-start (c.o.s.) and cancel-on-completion (c.o.c.) variants of redundancy-d scheduling and the fork-join model with heavy-tailed job sizes. We present bounds, which only differ in the pre-factor, for the tail probability of the response time in the case of the first-come first-served (FCFS) discipline. For the c.o.s. variant we restrict ourselves to redundancy-d scheduling, which is a special case of the fork-join model. In particular, for regularly varying job sizes with tail index -ν the tail index of the response time for the c.o.s. variant of redundancy-d equals -min\dcap(ν-1),ν\, where dcap = min\d,N-k\, N is the number of servers and k is the integer part of the load. This result indicates that for dcap < \fracνν-1 the waiting time component is dominant, whereas for dcap > \fracνν-1 the job size component is dominant. Thus, having d = \lceil min\\fracνν-1,N-k\ \rceil replicas is sufficient to achieve the optimal asymptotic tail behavior of the response time. For the c.o.c. variant of the fork-join(nF,nJ) model the tail index of the response time, under some assumptions on the load, equals 1-ν and 1-(nF+1-nJ)ν, for identical and i.i.d. replicas, respectively; here the waiting time component is always dominant.