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 (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 $-\nu$ the tail index of the response time for the c.o.s. variant of redundancy-$d$ equals $-\min \{d_{\mathrm{c}\mathrm{a}\mathrm{p}}(\nu -1),\nu \}$, where $d_{$\mathrm{c}\mathrm{a}\mathrm{p}$} = \min{d,N-k}$,$N$isthenumberofserversand$k$ is the integer part of the load. This result indicates that for $d_{\mathrm{c}\mathrm{a}\mathrm{p}}<\frac{\nu }{\nu -1}$ the waiting time component is dominant, whereas for $d_{$\mathrm{c}\mathrm{a}\mathrm{p}$} > \frac{\nu}{\nu-1}$thejobsizecomponentisdominant\mathrm{.}Thus,having$d = \lceil \min{\frac{\nu}{\nu-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($n_{\mathrm{F}},n_{\mathrm{J}}$) model the tail index of the response time, under some assumptions on the load, equals $1-\nu$ and $1-(n_{\mathrm{F}}+1-n_{\mathrm{J}})\nu$, for identical and i.i.d. replicas, respectively; here the waiting time component is always dominant.