Impossibility Results for Distributed Computing

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

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

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