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.