On a unifying product form framework for redundancy models

Abstract

In this paper, we present a unifying analysis for redundancy systems with cancel-on-start (c.o.s.) and cancel-on-complete (c.o.c) with exponentially distributed service requirements. With c.o.s.(c.o.c.) all redundant copies are removed as soon as one of the copies starts (completes) service. As a consequence, c.o.s. does not waste any computing resources, as opposed to c.o.c. We show that the c.o.s. model is equivalent to a queueing system with multi-type jobs and servers, which was analyzed in Visschers et al., (2012), and show that c.o.c. (under the assumption of i.i.d. copies) can be analyzed by a generalization of Visschers et al., (2012) where state-dependent departure rates are permitted. This allows us to show that the stationary distribution for both the c.o.c. and c.o.s. models has a product form. We give a detailed first-time analysis for c.o.s and derive a closed form expression for important metrics like mean number of jobs in the system, and probability of waiting. We also note that the c.o.s. model is equivalent to Join-Shortest-Work queue with power of d(JSW(d)). In the latter, an incoming job is dispatched to the server with smallest workload among D randomly chosen ones. Thus, all our results apply mutatis-mutandis to JSW(d). Comparing the performance of c.o.s. with that of c.o.c. with i.i.d. copies gives the unexpected conclusion (since c.o.s. does not waste any resources) that c.o.s. is worse in terms of mean number of jobs. As part of ancillary results, we illustrate that this is primarily due to the assumption of i.i.d. copies in case of c.o.c. (together with exponentially distributed requirements) and that such assumptions might lead to conclusions that are qualitatively different from that observed in practice.