Algorithms and Complexity of Distributed Computation

从简单的桌面pc甚至具有多核cpu的手机到高性能计算机集群和“云中的”系统，分布式计算系统必须处理由并发、异步和故障引起的问题。在这些情况下，设计时间和空间有效的算法，证明其正确性，并分析其复杂性是具有挑战性的任务。分布式系统中基本任务的算法和数据结构对未来高效、容错软件的开发至关重要。下限和不可能结果可以指导研究人员和软件开发人员努力构建高效的软件系统，并可以帮助硬件设计人员决定需要哪些硬件原语。

Distributed computing systems ranging from simple desktop PCs or even cell phones with multi-core CPUs to high-performance computer clusters and systems "in-the-cloud" have to deal with problems that arise from concurrency, asynchrony, and failures. In these settings, the design of time and space efficient algorithms, proof of their correctness, and analysis of their complexity are challenging tasks. Algorithms and data structures for fundamental tasks in distributed systems are critical for the future development of efficient and fault-tolerant software. Lower bounds and impossibility results can guide researchers and software developers in their efforts to build efficient software systems, and can help hardware designers to decide what hardware primitives are needed. In my research program I will devise new efficient algorithms and data structures for shared memory systems. I will try to find solutions for fundamental problems such as mutual exclusion, consensus, or the efficient and randomized implementation of strong primitives (e.g., compare-and-swap) from weaker ones. I will complement new algorithms with proofs of lower bounds in order to determine the time and space complexity of these problems. I will also investigate new methods for measuring the quality of randomized and deterministic shared memory algorithms and the complexity of problems. The classical worst-case analysis is often too pessimistic to predict the actual performance of programs in practice, and sometimes leads to complicated algorithms. Therefore, novel ways of theoretically predicting the performance of algorithms need to be developed and evaluated. Results of this research program will yield a better understanding of the system requirements of synchronization problems. Algorithms resulting from the research can be used as building blocks in software development, and lower bounds can help software and hardware developers making design decisions. Research on novel analytical performance measures for shared memory algorithms will directly and indirectly yield new solutions to synchronization problems, and improve the performance of systems relying on synchronization algorithms.