Diversity/Parallelism Trade-Off in Distributed Systems With Redundancy
Diversity/Parallelism Trade-Off in Distributed Systems With Redundancy
复制标题
DOI：
10.1109/tit.2021.3127920
复制
发表时间：
2020-10
影响因子：
2.5
通讯作者：
Pei Peng;E. Soljanin;P. Whiting
中科院分区：
文献类型：
--
作者：
Pei Peng;E. Soljanin;P. Whiting
分布式计算可以并行执行构成大型计算作业的较小任务。其目的是减少作业完成时间。然而，任务服务时间的随机波动会导致执行时间较长的任务分散。冗余提供了多样性，允许仅执行冗余任务的子集时完成作业，从而消除对分散任务的依赖。在资源受限的情况下（这里是固定数量的并行服务器），增加冗余会减少可用于并行的资源。在本文中，我们描述了多样性与并行性的权衡，并确定了复制、编码和拆分之间的最佳策略，从而最大限度地减少了预期作业完成时间。我们考虑三种常见的服务时间分布，并建立三个模型来描述这些分布随任务大小的缩放。我们发现具有不同缩放模型的不同分布在不同的冗余级别上运行最佳，因此需要非常不同的码率。
Distributed computing enables parallel execution of smaller tasks that make up a large computing job. Its purpose is to reduce the job completion time. However, random fluctuations in task service times lead to straggling tasks with long execution times. Redundancy provides diversity that allows job completion when only a subset of redundant tasks is executed, thus removing the dependency on the straggling tasks. Under constrained resources (here, a fixed number of parallel servers), increasing redundancy reduces the available resources for parallelism. In this paper, we characterize the diversity vs. parallelism trade-off and identify the optimal strategy among replication, coding, and splitting, which minimizes the expected job completion time. We consider three common service time distributions and establish three models that describe the scaling of these distributions with the task size. We find that different distributions with different scaling models operate optimally at different redundancy levels, thus requiring very different code rates.