TY - JOUR
T1 - The RESET and MARC Techniques, with Application to Multiserver-Job Analysis
AU - Grosof, Isaac
AU - Hong, Yige
AU - Harchol-Balter, Mor
AU - Scheller-Wolf, Alan
N1 - Publisher Copyright:
© 2024 Association for Computing Machinery. All rights reserved.
PY - 2024/2/23
Y1 - 2024/2/23
N2 - Multiserver-job (MSJ) systems, where jobs need to run concurrently across many servers, are increasingly common in practice. The default service ordering in many settings is First-Come First-Served (FCFS) service. Virtually all theoretical work on MSJ FCFS models focuses on characterizing the stability region, with almost nothing known about mean response time. We derive the first explicit characterization of mean response time in the MSJ FCFS system. Our formula characterizes mean response time up to an additive constant, which becomes negligible as arrival rate approaches throughput, and allows for general phase-type job durations. We derive our result by utilizing two key techniques: REduction to Saturated for Expected Time (RESET) and MArkovian Relative Completions (MARC). Using our novel RESET technique, we reduce the problem of characterizing mean response time in the MSJ FCFS system to an M/M/1 with Markovian service rate (MMSR). The Markov chain controlling the service rate is based on the saturated system, a simpler closed system which is far more analytically tractable. Unfortunately, the MMSR has no explicit characterization of mean response time. We therefore use our novel MARC technique to give the first explicit characterization of mean response time in the MMSR, again up to constant additive error. We specifically introduce the concept of “relative completions,” which is the cornerstone of our MARC technique.
AB - Multiserver-job (MSJ) systems, where jobs need to run concurrently across many servers, are increasingly common in practice. The default service ordering in many settings is First-Come First-Served (FCFS) service. Virtually all theoretical work on MSJ FCFS models focuses on characterizing the stability region, with almost nothing known about mean response time. We derive the first explicit characterization of mean response time in the MSJ FCFS system. Our formula characterizes mean response time up to an additive constant, which becomes negligible as arrival rate approaches throughput, and allows for general phase-type job durations. We derive our result by utilizing two key techniques: REduction to Saturated for Expected Time (RESET) and MArkovian Relative Completions (MARC). Using our novel RESET technique, we reduce the problem of characterizing mean response time in the MSJ FCFS system to an M/M/1 with Markovian service rate (MMSR). The Markov chain controlling the service rate is based on the saturated system, a simpler closed system which is far more analytically tractable. Unfortunately, the MMSR has no explicit characterization of mean response time. We therefore use our novel MARC technique to give the first explicit characterization of mean response time in the MMSR, again up to constant additive error. We specifically introduce the concept of “relative completions,” which is the cornerstone of our MARC technique.
UR - http://www.scopus.com/inward/record.url?scp=85190260037&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85190260037&partnerID=8YFLogxK
U2 - 10.1145/3649477.3649482
DO - 10.1145/3649477.3649482
M3 - Article
AN - SCOPUS:85190260037
SN - 0163-5999
VL - 51
SP - 6
EP - 7
JO - Performance Evaluation Review
JF - Performance Evaluation Review
IS - 4
ER -