Impossibility Results for Distributed Computing
Impossibility Results for Distributed Computing
批准号:
RGPIN-2020-04178
负责人:
Ellen, Faith
金额:
$4.66万
依托单位:
依托单位国家:
加拿大
项目类别:
Discovery Grants Program - Individual
财政年份:
2021
资助国家:
加拿大
项目状态:
已结题
起止时间:
2021-01-01 至 2022-12-31
中文摘要
分布式计算关注的是处理器之间的通信,通过相互传递消息或访问共享内存。进程可能以不同的速度运行,其中一些可能会失败。这使得很难设计分布式算法并证明它们是正确的。我的研究关注的是分布式计算中的某些基本问题无法解决,或者需要大量的资源(例如步骤或共享内存位置)来解决。此类问题的一个例子是共识,其中每个流程可能有不同的输入值,并且流程必须就这些值中的一个达成一致。如果每个进程(不失败的进程)必须在有限数量的共享内存读写中做出决定,则不可能确定地解决这个问题。对于随机化,存在一些算法,其中进程在预期的有限数量内决定读和写,但它们必须至少使用与进程一样多的共享内存位置。我最近用一种新技术证明,没有一种随机的共识算法可以使用更少的内存位置,从而解决了一个已经存在超过25年的问题。使用这种技术,我还证明了解决更一般问题所需的内存位置数量的界限,并使用了一些比读写更强大的操作。然而,目前还没有已知的算法可以达到这些界限。我打算改进我的新技术或设计其他技术来获得更好的边界,以匹配现有算法所能做的。这样的界限可以用来对不同操作的计算能力进行分类。证明不存在仅通过读和写来解决共识的确定性算法,使用了一种简单而优雅的技术,称为价参数。相反,对于一个相关的问题,集合一致性,使用复杂的组合拓扑技术证明了相同的结果。我最近证明了,基于更简单的技术,如价参数,无法证明这个结果。我计划扩展这项工作,以显示这些技术在证明其他问题和其他模型不可能解决时的局限性。我还想证明用于证明共享内存位置数量界限的标准技术不足以解决诸如集合协议之类的问题。最后,我打算研究共享内存位置的大小如何影响解决某些分布式计算问题所需的共享内存位置的数量。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Impossibility Results for Distributed Computing
-
批准号:RGPIN-2020-04178
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$4.66万
-
财政年份:2022
-
负责人:Ellen, Faith
-
依托单位:
Impossibility Results for Distributed Computing
-
批准号:RGPIN-2020-04178
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$4.66万
-
财政年份:2020
-
负责人:Ellen, Faith
-
依托单位:
Efficient Concurrent Data Structures
-
批准号:RGPIN-2015-05080
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$3.64万
-
财政年份:2019
-
负责人:Ellen, Faith
-
依托单位:
Efficient Concurrent Data Structures
-
批准号:RGPIN-2015-05080
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$3.64万
-
财政年份:2018
-
负责人:Ellen, Faith
-
依托单位:
Efficient Concurrent Data Structures
-
批准号:RGPIN-2015-05080
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$3.64万
-
财政年份:2017
-
负责人:Ellen, Faith
-
依托单位:
Efficient Concurrent Data Structures
-
批准号:RGPIN-2015-05080
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$3.64万
-
财政年份:2016
-
负责人:Ellen, Faith
-
依托单位:
Efficient Concurrent Data Structures
-
批准号:RGPIN-2015-05080
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$3.64万
-
财政年份:2015
-
负责人:Ellen, Faith
-
依托单位:
The complexity of fundamental problems in distributed computing
-
批准号:9176-2010
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$2.48万
-
财政年份:2014
-
负责人:Ellen, Faith
-
依托单位:
The complexity of fundamental problems in distributed computing
-
批准号:9176-2010
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$2.48万
-
财政年份:2013
-
负责人:Ellen, Faith
-
依托单位:
The complexity of fundamental problems in distributed computing
-
批准号:9176-2010
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$2.48万
-
财政年份:2012
-
负责人:Ellen, Faith
-
依托单位:
The complexity of fundamental problems in distributed computing
-
批准号:9176-2010
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$2.48万
-
财政年份:2011
-
负责人:Ellen, Faith
-
依托单位:
The complexity of fundamental problems in distributed computing
-
批准号:9176-2010
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$2.48万
-
财政年份:2010
-
负责人:Ellen, Faith
-
依托单位:
The complexity of distributed data structures
-
批准号:9176-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$4.44万
-
财政年份:2009
-
负责人:Ellen, Faith
-
依托单位:
The complexity of distributed data structures
-
批准号:9176-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$4.44万
-
财政年份:2008
-
负责人:Ellen, Faith
-
依托单位:
The complexity of distributed data structures
-
批准号:9176-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$4.44万
-
财政年份:2007
-
负责人:Ellen, Faith
-
依托单位:
海外基金