Abstract
Task replication has been advocated as a practical solution to reduce response times in parallel systems. The analysis of replication-based systems typically rests on some strong assumptions: Poisson arrivals, exponential service times, or independent service times of the replicas. This study is motivated not only by several studies which indicate that these assumptions are unrealistic, but also by some elementary observations highlighting some contriving behaviour. For instance, when service times are not exponential, adding a replication factor can stabilize an unstable system, i.e., having infinite delays, but a tempting higher replication factor can push the system back in a perilous unstable state. This behaviour disappears however if the replicas are sufficiently correlated, in which case any replication factor would even be detrimental.Motivated by the need to dispense with such common yet unrealistic and misleading assumptions, we provide a robust theoretical framework to compute stochastic bounds on response time distributions in general replication systems subject to Markovian arrivals, quite general service times, and correlated replicas. Numerical results show that our bounds are accurate and improve state-of-the-art bounds in the case of Markovian arrivals by as much as three orders of magnitude. We apply our results to a practical application and highlight that correctly setting the replication factor crucially depends on both the service time distributions of the replicas and the degree of correlation amongst.
Original language | English |
---|---|
Title of host publication | IEEE INFOCOM 2021 - IEEE Conference on Computer Communications |
Place of Publication | Piscataway |
Publisher | IEEE |
Number of pages | 10 |
ISBN (Electronic) | 978-1-6654-0325-2 |
ISBN (Print) | 978-1-6654-3131-6 |
DOIs | |
Publication status | Published - 2021 |
Event | INFOCOM 2021: IEEE International Conference on Computer Communications - Virtual/online event due to COVID-19, Virtual at Vancouver, Canada Duration: 10 May 2021 → 13 May 2021 https://infocom2021.ieee-infocom.org/ |
Publication series
Name | IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (IEEE INFOCOM 2021) |
---|---|
ISSN (Print) | 0743-166X |
Conference
Conference | INFOCOM 2021: IEEE International Conference on Computer Communications |
---|---|
Abbreviated title | INFOCOM 2021 |
Country/Territory | Canada |
City | Virtual at Vancouver |
Period | 10/05/21 → 13/05/21 |
Internet address |