On the Stability of Redundancy Models

• 成果类型: Article
• 署名作者: Anton, Elene; Ayesta, Urtzi; Jonckheere, Matthieu; Verloop, Ina Maria
• 署名单位: Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National Polytechnique de Toulouse; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP); Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National Polytechnique de Toulouse; Basque Foundation for Science; University of Basque Country; Consejo Nacional de Investigaciones Cientificas y Tecnicas (CONICET); University of Buenos Aires
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2030
• 发表日期: 2021
• 页码: 1540-1565
• 关键词: requests

摘要

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.