OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

On a unifying product form framework for redundancy models

Ayesta, Urtzi and Bodas, Tejas Prakash and Verloop, Maaike On a unifying product form framework for redundancy models. (2018) Performance Evaluation, 127-128. 93-119. ISSN 0166-5316

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1016/j.peva.2018.09.008


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.

Item Type:Article
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > IKERBASQUE (SPAIN)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Universidad del País Vasco - Euskal Herriko Unibertsitatea - EHU (SPAIN)
Laboratory name:
French "Agence Nationale de la Recherche (ANR)"
Deposited On:21 Feb 2019 15:20

Repository Staff Only: item control page