Efficient and reliable coded distributed computing

许多现代信息和通信技术应用程序需要大规模处理数据，需要进行无法在一台计算机上执行的大量计算。这导致了分布式计算的广泛使用，其中大量计算任务被分布在通信网络中的大量计算节点中。在现实生活中，其中一些计算节点由于软件/硬件故障、为网络处理其他任务、离开网络等原因而无法交付任务。这些分散的节点(通常约占处理节点的5%)会导致不可预测的网络性能，并可能显著延长作业完成时间。目前，以重复任务的形式实现冗余来对抗掉队。纠错码提供了以更低的成本打击掉队的机会，减少了通信负荷，提高了成功率，并具有更高的安全/隐私好处。它们还创造了通过网络使用大量极低成本的硬件在短时间内可靠地完成大量工作的机会。在这个项目中(I)我们将设计适合大规模分布式计算的各种低复杂度的纠错编码算法，从而使网络能够可靠地大规模处理数据；(Ii)我们将设计任务调度算法来优化分配和调度网络中的任务，以最大限度地减少完成时间/成本，并保证成功。我们预计该项目将通过开发编码的分布式计算和任务分配/调度算法来显著改进云服务，这些算法：(I)减少完成时间和通信成本，(Ii)非常高效地利用可用资源，(Iii)具有较低的实现复杂性，以及(Iv)提供更高的隐私/安全性。此外，我们的算法还可用于远程呈现、远程医疗、增强现实、分布式数据库管理系统、实时过程控制等实际应用中。

Many modern ICT applications work with data at scale and demand massive computations that cannot be performed in a single computer. This has led to the wide use of distributed computing, where a massive computational task is distributed among a large number of computing nodes in a communication network. In real-life, some of these computing nodes fail to deliver their task due to software/hardware failures, handling other tasks for the network, leaving the network, etc. These straggling nodes (typically around 5% of the processing nodes) result in unpredictable network performance and can significantly prolong job completion. Currently, redundancy in the form of repeating the tasks is implemented to combat the stragglers.Error-correcting codes offer an opportunity to combat stragglers at a much lower cost, reduced communication load, higher success rate, and with added security/privacy benefits. They also create the opportunity of using a large number of very low-cost hardware by the network to reliably finish a massive job in a short time. In this project(i) we will design various low-complexity error-correction coding algorithms that are feasible for large-scale distributed computing, hence enabling the network to handle data at scale reliably;(ii) we will design task scheduling algorithms that optimally distribute and schedule the tasks in the network in order to minimize the completion time/cost, with guaranteed success.We anticipate this project to significantly improve cloud services by developing coded distributed computation and task allocation/scheduling algorithms that (i) reduce the completion time and communication costs, (ii) very efficiently use the available resources, (iii) have low implementation complexity, and (iv) provide added privacy/security. In addition, our algorithms can be used in real-life applications such as telepresence, telehealth, augmented reality, distributed database management systems, real-time process control and more.