Back to Search
Start Over
On the Stability of Redundancy Models
- Source :
- Operations Research, Operations Research, INFORMS, In press, Operations Research, INFORMS, 2021, 69 (5), pp.1540-1565. ⟨10.1287/opre.2020.2030⟩
- Publication Year :
- 2021
- Publisher :
- Institute for Operations Research and the Management Sciences (INFORMS), 2021.
-
Abstract
- We investigate the stability condition of redundancy-$d$ multi-server 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 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 \emph{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 non-exponential service time distributions and heterogeneous server speeds.<br />38 pages, 21 figures
- Subjects :
- Mathematical optimization
Stochastic modelling
Computer science
Probability (math.PR)
Stability (learning theory)
020206 networking & telecommunications
02 engineering and technology
Management Science and Operations Research
Load balancing (computing)
01 natural sciences
Computer Science Applications
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
010104 statistics & probability
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Redundancy (engineering)
0101 mathematics
Mathematics - Probability
Subjects
Details
- ISSN :
- 15265463 and 0030364X
- Volume :
- 69
- Database :
- OpenAIRE
- Journal :
- Operations Research
- Accession number :
- edsair.doi.dedup.....3707a8ff743c4bdba66a9b40c07037ff