On the Stability of Redundancy Models

Elene Anton (), Urtzi Ayesta (), Matthieu Jonckheere () and Ina Maria Verloop ()
Additional contact information
Elene Anton: CNRS, IRIT, 31071 Toulouse, France; Université de Toulouse, INP, 31071 Toulouse, France
Urtzi Ayesta: CNRS, IRIT, 31071 Toulouse, France; Université de Toulouse, INP, 31071 Toulouse, France; IKERBASQUE, Basque Foundation for Science, 48011 Bilbao, Spain; UPV/EHU, University of the Basque Country, 20018 Donostia, Spain
Matthieu Jonckheere: Instituto de Cálculo–Conicet, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Ina Maria Verloop: CNRS, IRIT, 31071 Toulouse, France; Université de Toulouse, INP, 31071 Toulouse, France

Operations Research, 2021, vol. 69, issue 5, 1540-1565

Abstract: We investigate the stability condition of redundancy-d multiserver systems. Each server has its own queue and implements popular scheduling disciplines such as first-come-first-serve (FCFS), processor sharing (PS), and random order of service (ROS). New jobs arrive according to a Poisson process, and copies of each job are sent to d servers chosen uniformly at random. The service times of jobs are assumed to be exponentially distributed. A job departs as soon as one of its copies finishes service. Under the assumption that all d copies are independent and identically distributed (i.i.d.), we show that for PS and ROS (for FCFS it is already known), sending redundant copies does not reduce the stability region. Under the assumption that the d copies are identical, we show that (i) ROS does not reduce the stability region; (ii) FCFS reduces the stability region, which can be characterized through an associated saturated system; and (iii) PS severely reduces the stability region, which coincides with the system where all copies have to be fully served. The proofs are based on careful characterizations of scaling limits of the underlying stochastic process. Through simulations, we obtain interesting insights on the system’s performance for nonexponential service time distributions and heterogeneous server speeds.

Keywords: 68M20 / 60K25; Stochastic Models; redundancy model; load balancing; stochastic stability (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2030 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:5:p:1540-1565

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().