论文标题
通过FIFO服务纪律，对冗余-D的稳定区域的下限
A Lower Bound on the stability region of Redundancy-d with FIFO service discipline
论文作者
论文摘要
冗余-D（r（d））是一种负载平衡方法，用于将传入的作业路由k服务器路由，每个作业都有自己的队列。每个到达的作业都将复制到2 <= d <= k任务中，然后将其路由到随机选择的D服务器。当第一个任务完成服务时，剩余的D-1任务将被取消，而工作将离开系统。 尽管在某些条件下R（d）在某些条件下是已知的，可以大大提高工作完成时间，而与完全不使用冗余相比，在更基本的性能标准上知之甚少：r（d）排队系统稳定的R（d）排队系统的到达率是多少？在这种情况下，由于具有冗余和取消的系统的复杂动态，现有结果很少，并且仅限于任务的联合服务时间分布非常特殊的情况。 在本文中，我们在R（d）的稳定性区域提供了一个非平凡的，封闭形式的下限，以使用有限的第一和第二矩的任务的一般联合服务时间分布。我们考虑使用Bernoulli到达的离散时间系统，并假设作业是通过其到达顺序处理的。我们使用工作负载过程和二次Lyapunov功能来表征系统稳定的到达率集。虽然模拟结果表明我们的界限并不紧密，但它提供了易于检查的性能保证。
Redundancy-d (R(d)) is a load balancing method used to route incoming jobs to K servers, each with its own queue. Every arriving job is replicated into 2<=d<=K tasks, which are then routed to d servers chosen uniformly at random. When the first task finishes service, the remaining d-1 tasks are cancelled and the job departs the system. Despite the fact that R(d) is known, under certain conditions, to substantially improve job completion times compared to not using redundancy at all, little is known on a more fundamental performance criterion: what is the set of arrival rates under which the R(d) queueing system with FIFO service discipline is stable? In this context, due to the complex dynamics of systems with redundancy and cancellations, existing results are scarce and are limited to very special cases with respect to the joint service time distribution of tasks. In this paper we provide a non-trivial, closed form lower bound on the stability region of R(d) for a general joint service time distribution of tasks with finite first and second moments. We consider a discrete time system with Bernoulli arrivals and assume that jobs are processed by their order of arrival. We use the workload processes and a quadratic Lyapunov function to characterize the set of arrival rates for which the system is stable. While simulation results indicate our bound is not tight, it provides an easy-to-check performance guarantee.
