CIF: Small: Numerically-Stable Large-Scale Coded Distributed Computing

在这个以数据为中心的时代，计算机正在以前所未有的复杂规模收集和处理数量惊人的数据。在许多情况下，单个计算机/服务器没有足够的计算能力来快速处理如此大量的数据以执行手头的任务。加快计算速度的一种有效方法是将计算任务分解为更小的任务，并将更小的任务分配给许多工作节点。然后，可以在主节点上组装来自工作节点的结果，以完成原始计算任务。这种分布式方法有可能提供显著的加速；然而，这种方法的一个主要限制是，即使是单个分散的工作节点也会减慢整个过程。同样，单个工作节点出现故障或恶意，可能会在计算中引入错误，从而影响整个计算任务。因此，即使在存在掉队节点、故障节点或恶意节点的情况下，编码分布式计算也被用于加快计算速度。该项目将通过为分布式计算设计健壮的算法来推进编码分布式计算领域的最新技术，这些算法提供(i)对分散工作人员的弹性，（ii）对恶意或有缺陷的工作人员的弹性，以及（iii）可扩展性，即所设计算法的数值精度和实现复杂性将随着工作人员的数量有效扩展。这个项目有可能对现代计算基础设施的发展产生广泛的影响。该项目将设计和分析矩阵-矩阵乘法和多元多项式求值的数字稳定和计算效率高的编码分布式计算方案，这是机器学习和深度学习算法中经常使用的两个基本任务。重点将放在具有中等到大量工作节点的系统上。新颖的编码理论思想将被追求，强大的数学工具，从丰富的文献随机线性码，无率喷泉码，多维产品码，以及代数码的协同解码将被利用。将根据可容忍的离散工作节点的数量、可检测/纠正的工作节点计算中的对抗性或随机错误的数量、实现复杂性和数值稳定性来分析项目中开发的方案的性能。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

In this data-centric age, staggering amounts of data is being collected and processed using computers at unprecedented scales of complexity. In many situations, a single computer/server does not possess enough computational power to process such a large volume of data fast enough to execute the task at hand. A useful approach to speed up the computations is to break the computing task into smaller tasks and to distribute the smaller tasks among many worker nodes. The results from worker nodes can then be assembled at a master node to complete the original computing task. Such a distributed approach has the potential to provide a dramatic speed-up; however, a major limitation of this approach is that even a single straggling worker node can slow down the entire process. Similarly, a single faulty or malicious worker node can introduce errors in the computation, affecting the overall computation task. Coded distributed computing is therefore used to speed up computations even in the presence of stragglers and faulty or malicious nodes. This project will advance the state of the art in the domain of coded distributed computing by designing robust algorithms for distributed computation that provide (i) resilience to straggling workers, (ii) resilience to malicious or faulty workers, and (iii) scalability, i.e., the numerical accuracy and implementation complexity of the designed algorithms will scale efficiently with the number of workers. This project has the potential to have a broad impact on the development of modern computing infrastructures. This project will design and analyze numerically-stable and computationally-efficient coded distributed computing schemes for matrix-matrix multiplication and multivariate polynomial evaluation - two essential tasks frequently used in machine-learning and deep-learning algorithms. The focus will be on systems with a moderate to large number of worker nodes. Novel coding-theoretic ideas will be pursued, and powerful mathematical tools from the rich literature on random linear codes, rateless fountain codes, multi-dimensional product codes, as well as collaborative decoding of algebraic codes will be leveraged. The performance of the schemes developed in the project will be analyzed in terms of the number of straggling worker nodes that can be tolerated, the number of adversarial or random errors in the computations of the worker nodes that can be detected/corrected, the implementation complexity and the numerical stability.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.