Practical analysis of replication-based systems

Florin Ciucu, Felix Poloczek, Lydia Y. Chen, Martin Chan

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


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 languageEnglish
Title of host publicationIEEE INFOCOM 2021 - IEEE Conference on Computer Communications
Place of PublicationPiscataway
Number of pages10
ISBN (Electronic)978-1-6654-0325-2
ISBN (Print)978-1-6654-3131-6
Publication statusPublished - 2021
EventINFOCOM 2021: IEEE International Conference on Computer Communications - Virtual/online event due to COVID-19, Virtual at Vancouver, Canada
Duration: 10 May 202113 May 2021

Publication series

ISSN (Print)0743-166X


ConferenceINFOCOM 2021: IEEE International Conference on Computer Communications
Abbreviated titleINFOCOM 2021
CityVirtual at Vancouver
Internet address

Cite this