CIF: Small: Leveraging Coding Techniques for Distributed Computing

在被称为数据中心的专门位置处理海量数据的计算机处理器集群在工业界和学术界无处不在。分布式集群的使用是必要的，而不是奢侈品，因为许多现代数据集太大，无法存储在单个计算机的内存或磁盘中。然而，使用这样的集群来快速有效地获得答案会带来许多新的挑战。这些包括处理诸如缓慢或故障的处理器(即，工作节点)的问题，并考虑这些工作节点为了协作执行作业而在它们之间进行通信的时间。这类问题非常关键，因为众所周知，对于如此大规模的系统，工作节点故障是常态，而不是例外。该项目将研究大规模分布式计算集群稳健和高效运行的方法类别。此外，该项目将对研究生和本科生进行数据分析方面的培训，并使用行业标准技术处理这些集群。该项目的总体目标是利用编码理论思想使分布式计算对落后者(速度较慢或出现故障的工作节点)具有健壮性，并减少分布式计算范例(如MapReduce和Spark)的通信开销。虽然最近已经有一些关于分布式矩阵计算的掉队缓解的主题的工作，但以前的大部分工作都是通过将掉队完全视为节点故障来进行的。这个项目将研究利用缓慢(但不是失败的)落后者的严格技术。特别是，在为我们的系统设计代码时，将考虑工作节点内计算的顺序性质。该项目的第二部分将处理有关分布式矩阵计算中恢复的数值稳定性的问题。针对该问题而提出的几种众所周知的擦除码在该度量上的性能相当差。该项目将设计对缓解掉队有用的代码类，并从数值稳定性的角度对其进行分析。该项目的最后部分将解决在分布式集群上执行作业所使用的类MapReduce型系统中减少混洗阶段流量的问题。这一领域以前的工作提出了信息理论上最优的技术(在适当的模型下)。关于先前工作的一个主要假设是，工作可以被分成任意小的部分。然而，在实际系统中，这一假设严重限制了总作业执行时间的实际收益。这个项目将研究一大类技术，通过利用适当定义的线性分组码的特性来减少洗牌阶段的流量和总体作业执行时间。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Clusters of computer processors that process huge amounts of data at specialized locations called data centers are ubiquitous in both industry and academia. The usage of distributed clusters is a necessity rather than a luxury since many modern datasets are too large to be stored in the memory or disk of a single computer. However, using such clusters to obtain answers quickly and efficiently presents many new challenges. These include dealing with issues such as slow or failed processors (ie., worker nodes) and taking into account the time for these worker nodes to communicate among themselves for collaboratively executing a job. Such issues are critical, as it is well-recognized that for such large scale systems, worker node failures are the norm rather than the exception. The project will investigate classes of methods for the robust and efficient operation of large-scale distributed computing clusters. Furthermore, the project will train graduate and undergraduate students in data analytics and in using industry standard techniques for working with these clusters.The overarching goal of this project is to leverage coding-theoretic ideas to make distributed computation robust to stragglers (slow or failed worker nodes) and reduce the communication overhead of distributed computing paradigms such as MapReduce and Spark. While there has been some recent work on the topic of straggler mitigation for distributed matrix computations, the majority of prior work proceeds by treating stragglers exclusively as node failures. This project will investigate rigorous techniques for leveraging slow (but not failed) stragglers. In particular, the sequential nature of computation within a worker node will be taken into account when designing codes for our systems. The second part of the project will deal with issues around the numerical stability of recovery within distributed matrix computation. Several well-known erasure codes that have been proposed for this problem perform rather poorly on this metric. The project will design classes of codes that are useful in straggler mitigation and analyze them through the lens of numerical stability. The last part of the project will address the reduction of shuffle phase traffic in MapReduce-like systems that are used for executing jobs over distributed clusters. Prior work in this area proposes techniques that are information-theoretically optimal (under an appropriate model). A major assumption of prior work is that jobs can be split into arbitrarily small parts. However, in practical systems, this assumption severely limits the actual gain in the overall job execution time. This project will study a large class of techniques that reduce shuffle phase traffic and the overall job execution time by leveraging the properties of suitably defined linear block codes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.