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

消息传递、共享内存和混合系统的分布式计算原理

• 批准号: RGPIN-2022-03304
• 负责人: Toueg, Sam
• 金额: $ 2.11万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750062
• 关键词: Principles; Distributed; Computing; Message; Passing

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.

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