Modern computationally-heavy applications are often time-sensitive, demanding distributed strategies to accelerate them. On the other hand, distributed computing suffers from the bottleneck of slow workers in practice. Distributed coded computing is an attractive solution that adds redundancy such that a subset of distributed computations suffices to obtain the final result. However, the final result is still either obtained within a desired time or not, and for the latter, the resources that are spent are wasted. In this paper, we introduce the novel concept of layered-resolution distributed coded computations such that lower resolutions of the final result are obtained from collective results of the workers -- at an earlier stage than the final result. This innovation makes it possible to have more effective deadline-based systems, since even if a computational job is terminated because of timing, an approximated version of the final result can be released. Based on our theoretical and empirical results, the average execution delay for the first resolution is notably smaller than the one for the final resolution. Moreover, the probability of meeting a deadline is one for the first resolution in a setting where the final resolution exceeds the deadline almost all the time, reducing the success rate of the systems with no layering.
翻译:现代的计算重度应用往往具有时间敏感性,要求分配策略加速这些应用。另一方面,分布式计算在实际操作中受到慢工的瓶颈。分配式编码计算是一个有吸引力的解决方案,它增加了冗余,使一组分配式计算方法足以获得最终结果。然而,最终结果要么是在理想的时间内获得,要么不是在最后结果中获得,而对于后者来说,所花费的资源是浪费的。在本文件中,我们引入了分层分辨率分布式编码计算的新概念,这样,在工人集体结果 -- -- 比最终结果早的阶段 -- -- 获得较低的最终结果分辨率。这种创新使得有可能建立更有效的基于最后期限的系统,因为即使计算工作因时间而终止,最终结果的大概版本也可以发布。根据我们的理论和实验结果,第一个决议的平均执行延迟明显小于最后决议的延迟。此外,在确定最终决议几乎全部超过最后期限的情况下,实现第一个决议的最后期限的可能性是第一个决议的最后期限,从而降低系统的成功率,而没有一层系统的成功率。