On Principles of Distributed Computing for Message-Passing, Shared-Memory, and Hybrid Systems

本研究的长期目标是研究分布式计算中的基本问题，分布式计算是计算机科学的一个领域，它解决了当一组通信进程合作共同执行计算任务时出现的问题。正如我们之前的工作一样，我们的研究将集中在分布式计算的两个核心问题上：同步，确保进程在访问共享资源时不会相互阻碍；容错，确保即使系统的一些组件出现故障，系统也能继续正常工作。提议的研究将包括消息传递系统，其中进程通过交换消息进行通信，共享内存系统，其中进程通过访问共享对象进行通信，以及混合系统，其中进程既可以交换消息又可以共享内存。本研究主要是理论性的，但也受到实际问题和考虑的推动。一些预期结果有望有直接应用。作为这项研究的一部分，我们计划研究共享对象的新的活动性和公平性要求。直观地说，活动性保证（部分或全部）访问共享对象的进程在有限的时间内从该对象获得响应，公平性确保每个进程能够在共享对象上完成的操作数量与其相对速度成正比。特别是，我们将探索一个新的参数化活跃性，它确保对于每个对象操作类型T，至少k个通过应用类型T的操作访问对象的进程保证取得进展。我们的目标是推导出实现对象的算法，既满足这一属性，又公平。我们还计划探索使用高度同步的外部时钟（例如GPS时钟）来有效地解决部分异步系统中的问题。我们的出发点是一种有效的算法，它使用这种时钟来维护地理分布的、容易发生故障的消息传递系统中高度一致的对象副本（比如数据存储）。我们将研究如何将我们在该算法中使用的基于时钟的技术有效地应用于解决其他问题。我们还想通过推导性能下限来了解这种配备时钟的系统的局限性。在技术进步的推动下，我们还致力于解决混合系统的问题，并获得进程既可以交换消息又可以共享内存的性能下限。为此，我们计划扩展我们最近的工作，我们在这些系统中解决了一些基本问题，包括共识。这些解决方案是最优的，因为它们可以容忍最大数量的进程崩溃。我们的目标是通过容忍额外类型的流程故障以及它们访问的共享对象的故障来提高解决方案的容错性。

The long term objective of this research is to study fundamental problems in distributed computing, the area of computer science addressing the problems that arise when a set of communicating processes cooperate to carry out jointly a computational task. As in our previous work, our research will focus on the two central concerns of distributed computing: synchronization, which ensures that processes do not impede each other as they access shared resources, and fault-tolerance, which ensures that the system continues to work correctly even if some of its components fail. The proposed research will encompass message-passing systems, where processes communicate by exchanging messages, shared-memory systems, where processes communicate by accessing shared objects, and also hybrid systems where processes can both exchange messages and share memory. This research is primarily theoretical but it is motivated by practical problems and considerations. Some anticipated results are expected to have direct applications. As part of this research, we plan to investigate new liveness and fairness requirements for shared objects. Intuitively, liveness guarantees that (some or all) processes that access a shared object get a response from the object within a bounded time, and fairness ensures that the number of operations that each process is able to complete on a shared object is proportional to its relative speed. In particular, we will explore a new parametrized liveness property which ensures that, for every object operation type T, at least k processes accessing an object by applying operations of type T are guaranteed to make progress. The goal is to derive algorithms for implementing objects that satisfy this property and are also fair. We also plan to explore the use of highly synchronized external clocks (e.g., GPS clocks) to solve problems efficiently in systems that are otherwise partially asynchronous. Our starting point is an efficient algorithm that uses such clocks to maintain highly-consistent object replicas (such as data stores) in geographically distributed message-passing systems that are prone to failures. We will investigate how the clock-based techniques that we used in this algorithm can be applied to solve other problems efficiently. We also want to understand the limitation of such clock-equipped systems by deriving performance lower bounds. Motivated by technological advances, we also aim to solve problems and obtain performance lower bounds for hybrid systems where processes can both exchange messages and share memory. To do so we plan to extend our recent work where we solved some fundamental problems, including consensus, in such systems. These solutions are optimal in the sense that they tolerate the maximum number of process crashes possible. Our goal is to increase the fault-tolerance of our solutions by tolerating additional types of process failures, and also by tolerating failures of the shared objects they access.