Tackling Latency via Replication in Distributed Systems - Harrison,PG; Qiu,Z; Perez,JF (ACM, 2016)
Consistently high reliability and low latency are twin requirementscommon to many forms of distributed processing;for example, server farms and mirrored storage access.To address them, we consider replication of requests withcanceling – i.e. initiate multiple concurrent replicas of a requestand use the first successful result returned, cancelingall outstanding replicas. This scheme has been studied recently,but mostly for systems with a single central queue,while server farms exploit distributed resources for scalabilityand robustness. We develop an approximate stochasticmodel to determine the response-time distribution in a systemwith distributed queues, and compare its performanceagainst its centralized counterpart. Validation against simulationindicates that our model is accurate for not only themean response time but also its percentiles, which are particularlyrelevant for deadline-driven applications. Further,we show that in the distributed set-up, replication with cancelinghas the potential to reduce response times, even atrelatively high utilization. We also find that it offers responsetimes close to those of the centralized system, especiallyat medium-to-high request reliability. These findingssupport the use of replication with canceling as an effectivemechanism for both fault- and delay-tolerance.