Impossibility Results for Distributed Computing

分布式计算的不可能性结果

• 批准号: RGPIN-2020-04178
• 负责人: Ellen, Faith
• 金额: $ 4.66万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750030
• 关键词: Impossibility; Results; Distributed; Computing

Distributed computing is concerned with processors that communicate with one another, either by passing messages to one another or by accessing shared memory. Processes may run at different speeds and some of them may fail. This makes it difficult to design distributed algorithms and prove them correct. My research is concerned with showing that certain fundamental problems in distributed computing cannot be solved or require large amounts of resources (such as steps or shared memory locations) to be solved. An example of such a problem is consensus, where each process has a possibly different input value and the processes must agree on one of these values. It is impossible to solve deterministically if every process (that does not fail) must decide within a finite number of reads and writes of shared memory. With randomization, there are algorithms in which processes decide within an expected finite number of reads and writes, but they must use at least as many shared memory locations as processes. I recently proved, using a new technique, that no randomized algorithm for consensus can use fewer memory locations, closing a problem that had been open for more than 25 years. Using this technique, I also proved bounds on the number of memory locations needed for solving more general problems and using some more powerful operations than read and write. However, there are no known algorithms which achieve these bounds. I intend to refine my new technique or design other techniques to get better bounds, matching what existing algorithms can do. Such bounds can be used to classify the computational power of different operations. The proof that there is no deterministic algorithm solving consensus with only reads and writes uses a simple and elegant technique called a valency argument. In contrast, the same result for a related problem, set agreement, was proved using sophisticated techniques from combinatorial topology. I recently proved that there is no proof of this result based on simpler techniques such as valency arguments. I plan to extend this work to show the limitations of these techniques for proving the impossibility of solving other problems and in other models. I also want to prove that standard techniques for proving bounds on the number of shared memory locations are not sufficient for problems such as set agreement. Finally, I intend to study how the size of shared memory locations affects the number of shared memory locations needed to solve certain distributed computing problems.

分布式计算与处理器之间的通信有关，或者通过相互传递消息，或者通过访问共享内存。进程可能以不同的速度运行，其中一些进程可能会失败。这使得很难设计分布式算法并证明它们是正确的。 我的研究是关于证明分布式计算中的某些基本问题无法解决或需要大量资源（如步骤或共享内存位置）才能解决。这种问题的一个例子是共识，其中每个过程都有可能不同的输入值，并且过程必须就这些值之一达成一致。如果每个进程（不会失败的进程）都必须在有限的共享内存读写次数内做出决定，那么就不可能确定地解决这个问题。对于随机化，存在一些算法，其中进程在预期的有限数量的读取和写入内进行决策，但它们必须使用至少与进程一样多的共享内存位置。我最近使用一种新技术证明了，没有一种共识随机算法可以使用更少的内存位置，解决了一个已经开放了25年的问题。使用这种技术，我还证明了解决更一般的问题和使用一些比读和写更强大的操作所需的内存位置数量的界限。然而，没有已知的算法可以达到这些界限。我打算改进我的新技术或设计其他技术，以获得更好的界限，匹配现有的算法可以做什么。这样的界限可以用来对不同操作的计算能力进行分类。证明不存在只通过读写来解决共识的确定性算法，使用了一种简单而优雅的技术，称为价参数。与此相反，一个相关的问题，集协议，证明了使用复杂的技术从组合拓扑相同的结果。我最近证明，基于化合价参数等更简单的技术，无法证明这一结果。我计划扩展这项工作，以显示这些技术的局限性，证明不可能解决其他问题和其他模型。我还想证明，标准的技术证明共享内存位置的数量的界限是不够的问题，如设置协议。最后，我打算研究共享内存位置的大小如何影响解决某些分布式计算问题所需的共享内存位置的数量。