Supervised Distributed Computing

John Augustine

doi:10.1007/978-3-031-99872-0_4

2026-01-01

PRE

John Augustine

Christian Scheideler

Julian Werthmann *

DOI：10.1007/978-3-031-99872-0_4

原文链接

原文求助

摘要

En 中文

我们介绍了一种分布式计算的新框架，该框架扩展并改进了多线程计算的标准主-从调度方法。在此框架中，存在不同角色：一个监督者、一个源、一个目标以及一组工作者。最初，源存储某个计算问题的实例I，而在结束时，目标应存储该实例的正确解S(I)。我们假设计算S(I)所需的工作可以建模为一个有向无环图G=(V, E)，其中V是任务集合，且当且仅当任务ω需要从任务v获取信息才能执行时，(v, ω)是E的元素。给定G，监督者的角色是通过将其分配给工作者来调度图中任务的执行。如果所有工作者都是诚实的，信息可以在工作者之间交换，且工作者可以访问源和目标，那么监督者只需要知道G即可成功调度计算。也就是说，监督者无需像标准主-从方法那样自行处理任何数据，这一巨大优势在于任务可以在大型分布式环境中大规模并行运行，而不会使监督者成为瓶颈。但如果一部分固定的工作者是恶意的呢？有趣的是，我们证明在某些假设下，数据无关的调度方法甚至可以在恶意设置中工作，而不会（渐近地）增加通信和计算所需的工作量。我们通过为监督矩阵乘法和排序提出具体解决方案来证明这些假设的有效性。

Keyword:

Distributed Computing

Fault Tolerance

Peer-to-peer Networks