CIF:Medium:Collaborative Research: Foundations of Coding for Modern Distributed Computing

编码和信息理论提供了一个非常丰富的知识体系，从理论到概念，再到用于创建、利用和删除的结构。“冗余”已经彻底改变了数字时代。这个项目将这些概念和技术应用到一个新的领域：大规模分布式计算。大规模分布式计算系统的现代范例是由由多达数万或数十万台机器组成的集群的计算“向外扩展”驱动的。因此，有大量的资源冗余可以被利用。该项目开发了“编码计算”的基础，这是一个将编码与分布式计算相结合的新框架，以克服限制当今大规模分布式计算平台性能的几个基本挑战。该项目的研究成果将纳入教育，并广泛传播。该项目采用原则性和基础性的方法来提供统一的编码框架，以解决大规模分布式计算中的三个关键挑战：由于离散节点导致的显著延迟；计算节点间通信负荷大；以及大量的输入数据集。特别地，提出了分布式计算的三个新的编码概念：注入计算冗余的编码以减轻离散问题；用编码代替局部计算，实现全局通信；以及为统计原理的数据草图编码。本文还研究了代码在快速绘制和对离散节点延迟和通信瓶颈提供鲁棒性方面的统一作用。

Coding and information theory provide a very rich body of knowledge from theory to concepts to constructions for creating, leveraging, and removing ?redundancy" in ways that have revolutionized the digital era. This project brings these concepts and techniques to bear in a new field: large-scale distributed computing. The modern paradigm for large-scale distributed computing systems is driven by  "scaling out" of computations across clusters consisting of as many as tens or hundreds of thousands of machines. As such, there is an abundance of resource redundancy that can be exploited. This project develops a foundation for "coded computing", a new framework that combines coding with distributed computing to overcome several fundamental challenges limiting the performance of today's large-scale distributed computing platforms. The research outcomes of the project will be integrated into education and will be disseminated broadly. This project takes a principled and foundational approach to providing a unified coding framework to tackle three key challenges in large-scale distributed computing: significant delays due to straggling nodes; large communication loads between computing nodes; and massive input data-sets. In particular, three novel coding concepts are proposed for distributed computing: coding for injecting computation redundancy to mitigate straggler issues; coding to trade local computation with global communication; and coding for statistically principled data sketching. The unified role of codes in both doing fast sketching and in providing robustness to straggler node delays and communication bottlenecks is also studied.