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.