Design and Complexity of Distributed Algorithms

从简单的台式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 data structures such as concurrent dictionaries, and new implementations of strong synchronization primitives, e.g., multi-word compare-and-swap and snapshot objects. 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 algorithm design and analysis methods. The classical approach to allow no room for error may limit algorithm design, and can lead to inefficiencies. I will study concurrent Monte Carlo algorithms that may produce errors or faults in very rare cases, but perform better than their error-free counterparts. Related to that will be my study of the recently defined allocate-on-access space requirements of shared memory algorithms: Many fundamental problems are known to require a large amount of (memory or disk) space in the worst-case. But these worst-case scenarios may be very improbable. The significance of the worst-case space complexity is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems. The allocate-on-access measure is a more realistic approach to measuring actual space usage on modern storage systems without being overly pessimistic. 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 Monte Carlo algorithms and the allocate-on-access space complexity will directly and indirectly yield new solutions to synchronization problems, and improve the performance of systems relying on such algorithms.