论文标题
通过冗余的协同作用：自适应复制策略和基本限制
Synergy via Redundancy: Adaptive Replication Strategies and Fundamental Limits
论文作者
论文摘要
多服务器系统的最大可能吞吐量（或工作完成率）通常是单个服务器的服务率的总和。最近的工作表明，启动工作的多个复制品并在一个副本完成后立即取消它们可以提高吞吐量，尤其是当服务时间分布具有较高的可变性时。这意味着，冗余实际上可以在服务器之间产生协同作用，使其整体吞吐量大于单个服务器的总和。这项工作旨在找到通过工作复制实现的吞吐量提升的基本限制以及实现它的最佳复制政策。尽管大多数先前的作品都考虑了前期复制策略，但我们将可能的策略集扩大到延迟发布的副本。搜索最佳自适应复制策略可以作为马尔可夫决策过程提出，我们建议我们提出两个近视复制策略MaxRate和Adarep，以自适应地复制作业。为了量化这些政策和其他政策的最佳差距，我们根据服务能力得出上限，这为具有冗余的排队系统的吞吐量提供了基本限制。
The maximum possible throughput (or the rate of job completion) of a multi-server system is typically the sum of the service rates of individual servers. Recent work shows that launching multiple replicas of a job and canceling them as soon as one copy finishes can boost the throughput, especially when the service time distribution has high variability. This means that redundancy can, in fact, create synergy among servers such that their overall throughput is greater than the sum of individual servers. This work seeks to find the fundamental limit of the throughput boost achieved by job replication and the optimal replication policy to achieve it. While most previous works consider upfront replication policies, we expand the set of possible policies to delayed launch of replicas. The search for the optimal adaptive replication policy can be formulated as a Markov Decision Process, using which we propose two myopic replication policies, MaxRate and AdaRep, to adaptively replicate jobs. In order to quantify the optimality gap of these and other policies, we derive upper bounds on the service capacity, which provide fundamental limits on the throughput of queueing systems with redundancy.
