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

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

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.