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.

这项研究的长期目标是研究分布式计算中的基本问题，即计算机科学领域，解决了一组交流过程合作以共同执行计算任务时出现的问题。与我们以前的工作一样，我们的研究将重点关注分布式计算的两个主要问题：同步，这确保过程在访问共享资源和容忍度时不会互相阻碍，这确保了系统即使某些组件失败，也可以继续正常工作。拟议的研究将包含消息通讯系统，其中流程通过交换消息，共享内存系统，通过访问共享对象进行通信的过程以及过程既可以交换消息和共享存储器的过程进行通信的过程进行通信。这项研究主要是理论上的，但它是出于实际问题和考虑因素的动机。一些预期的结果预计将有直接的申请。作为这项研究的一部分，我们计划调查共享对象的新的失败和公平要求。直觉上，LIVISE保证（某些或全部）访问共享对象的过程在有限的时间内从对象中获取响应，并且公平性确保每个过程能够在共享对象上完成的操作数量与其相对速度成正比。特别是，我们将探索一个新的参数化livese属性，该属性可确保每种对象操作类型操作至少通过应用T类型操作来访问对象的k个过程可以确保取得进展。目的是得出用于实现满足该属性并且也公平的对象的算法。我们还计划探索使用高度同步的外时钟（例如GPS时钟）的使用，以在某些部分异步的系统中有效地解决问题。我们的起点是一种有效的算法，该算法使用此类时钟来维护易于发生故障的地理分布式消息串联系统中的高度一致的对象复制品（例如数据存储）。我们将研究如何应用我们在本算法中使用的基于时钟的技术有效地解决其他问题。我们还想通过得出性能下限来了解此类时钟系统的局限性。在技​​术进步的推动下，我们还旨在解决问题并获得混合系统的性能下限，这些过程既可以交换消息又可以共享记忆。为此，我们计划扩展我们最近解决了一些基本问题，包括共识，在这种系统中。这些解决方案是最佳的，因为它们可以忍受最大的过程崩溃数量。我们的目标是通过容忍其他类型的流程故障以及容忍其访问的共享对象的故障来增加解决方案的故障耐受性。