Efficient and reliable coded distributed computing

高效可靠的编码分布式计算

• 批准号: 570977-2021
• 负责人: Ardakani, Masoud
• 金额: $ 3.64万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Alliance Grants
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=722762
• 关键词: Efficient; reliable; coded; distributed; computing

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.

许多现代 ICT 应用程序都需要处理大规模数据，并需要单台计算机无法执行的大量计算。这导致了分布式计算的广泛使用，其中大量计算任务分布在通信网络中的大量计算节点中。在现实生活中，其中一些计算节点由于软件/硬件故障、处理网络的其他任务、离开网络等而无法交付任务。这些掉队节点（通常占处理节点的 5% 左右）导致不可预测的网络性能，可以显着延长作业完成时间。目前，采用重复任务形式的冗余来对抗掉队者。纠错码提供了以更低的成本、减少的通信负载、更高的成功率以及增加的安全/隐私优势来对抗掉队者的机会。它们还创造了通过网络使用大量成本极低的硬件在短时间内可靠地完成大量工作的机会。在这个项目中（i）我们将设计各种适用于大规模分布式计算的低复杂度纠错编码算法，从而使网络能够可靠地处理大规模数据；（ii）我们将设计最优的任务调度算法分配和调度网络中的任务，以最大程度地减少完成时间/成本，并保证成功。我们预计该项目将通过开发编码分布式计算和任务分配/调度算法（i）减少完成时间来显着改善云服务和沟通成本，(ii) 非常有效使用可用资源，(iii) 实现复杂性较低，(iv) 提供额外的隐私/安全性。此外，我们的算法还可用于现实生活中的应用，例如远程呈现、远程医疗、增强现实、分布式数据库管理系统、实时过程控制等。