Impossibility Results for 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.