Fork–join and redundancy systems with heavy-tailed job sizes

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 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 { d_cap(ν- 1) , ν} , where d_cap= 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<νν-1 the waiting time component is dominant, whereas for dcap>νν-1 the job size component is dominant. Thus, having d=⌈min{νν-1,N-k}⌉ replicas is sufficient to achieve the optimal asymptotic tail behavior of the response time. For the c.o.c. variant of the fork–join (n_F, n_J) model, the tail index of the response time, under some assumptions on the load, equals 1 - ν and 1 - (n_F+ 1 - n_J) ν, for identical and i.i.d. replicas, respectively; here, the waiting time component is always dominant.