2020/12/25 by Gauri Joshi, Joshi, Gauri, Dhruva Kaushal +1
Business, Management and Accounting · Computer Science · #Advanced Queuing Theory Analysis #Age of Information Optimization #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.2012.13608
The maximum possible throughput (or the rate of job completion) of a\nmulti-server system is typically the sum of the service rates of individual\nservers. Recent work shows that launching multiple replicas of a job and\ncanceling them as soon as one copy finishes can boost the throughput,\nespecially when the service time distribution has high variability. This means\nthat redundancy can, in fact, create synergy among servers such that their\noverall throughput is greater than the sum of individual servers. This work\nseeks to find the fundamental limit of the throughput boost achieved by job\nreplication and the optimal replication policy to achieve it. While most\nprevious works consider upfront replication policies, we expand the set of\npossible policies to delayed launch of replicas. The search for the optimal\nadaptive replication policy can be formulated as a Markov Decision Process,\nusing which we propose two myopic replication policies, MaxRate and AdaRep, to\nadaptively replicate jobs. In order to quantify the optimality gap of these and\nother policies, we derive upper bounds on the service capacity, which provide\nfundamental limits on the throughput of queueing systems with redundancy.\n