Algorithms, abstractions and models for distributed computing.

分布式计算的算法、抽象和模型。

• 批准号: RGPIN-2014-05296
• 负责人: Toueg, Sam
• 金额: $ 2.84万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708148
• 关键词: Algorithms; abstractions; models; distributed; computing.

We plan to work on fundamental problems, abstractions and models in distributed computing. This research will encompass both message-passing models (which are suited to geographically distributed systems such as peer-to-peer, mobile, or cloud systems) and shared-memory models (which are suited to multicore systems). One goal is to derive better algorithms and abstractions that simplify the design or improve the performance of distributed systems. Another goal is to compare, and where possible unify, some of the many models and related results in this area. We now briefly summarize some of the proposed work towards these goals. Linearizable wait-free shared objects are a powerful abstraction for building asynchronous shared-memory distributed systems: they behave as if they are accessed sequentially, and every non-faulty process that invokes an operation on a wait-free object is guaranteed to get a response even if other processes are slow or crash. Implementing such objects, however, can be difficult and inefficient, and this has led to the study of objects that have weaker (though still useful) semantics but have easier and more efficient implementations. In this vein, we propose to continue our work on abortable objects, i.e., objects where operations that interfere with each other may abort without taking effect. This is reminiscent of the simple and attractive behaviour of transactional memory, database transactions, and abortable mutual exclusion --- techniques in which a process can, under contention, ``bail out'' of the computation without leaving a trace. Our preliminary work on abortable objects showed that abortable objects are inherently different from ordinary ones and need to be studied on their own. We propose to continue this work to better understand abortable objects, and to compare them to ordinary (i.e., non-abortable) objects in terms of power and implementation efficiency. Several fundamental problems that cannot be solved in fully asynchronous systems with failures can be solved in systems with additional properties, such as partial synchrony, failure detection, and fair schedulers. Recent research suggests that many of these systems are closely related (e.g., several failure detectors have been shown to be equivalent to fair schedulers) but considerable work remains to be done to better understand their similarities and differences. We will continue to investigate and compare these systems in an effort to unify and better understand the many models and results in the area. In many distributed systems, some strong assumptions, e.g., that processes are synchronous and do not crash, can hold for relatively long periods of time. Furthermore, algorithms that make such strong assumptions can be very efficient, but they may fail in the relatively rare cases when these assumptions are violated. To take advantage of this, one can first run a ``primary'' algorithm that is very efficient because it relies on strong assumptions, and then, in the rare cases when the primary algorithm fails, fall back on a less efficient ``backup'' algorithm that relies on weaker assumptions; this is the basic idea of ``speculative computing''. In preliminary work based on this approach, we derived speculative algorithms for the fundamental problem of consensus in systems with process crash failures. We propose to extend and generalize this initial work in several directions, for example to solve problems other than consensus, to tolerate more than just crash failures, and to investigate the efficient implementation of shared objects based on speculative computing.

我们计划在分布式计算中处理基本问题，抽象和模型。这项研究将涵盖通信模型（适用于地理分布式系统，例如点对点，移动或云系统）和共享内存模型（适用于多层系统）。一个目标是得出更好的算法和抽象来简化设计或改善分布式系统的性能。另一个目标是比较该领域的众多模型和相关结果中的一些，并在可能的情况下进行比较。现在，我们简要总结了针对这些目标的一些拟议工作。 可线化的无候补共享对象是一个有力的抽象，用于构建异步共享内存分布式系统：它们的行为好像它们被依次访问，并且每个非故障的过程都可以保证，即使其他进程很慢或崩溃，也可以保证在无候补对象上调用操作。但是，实施此类对象可能是困难且效率低下的，这导致研究了语义较弱（尽管仍然有用）但具有更易于实现的对象。在这种情况下，我们建议继续我们在可流产的物体上的工作，即，在彼此干扰的操作中可能会流产而无生效的对象。这让人联想到交易记忆，数据库交易的简单而有吸引力的行为以及可流产的相互排斥---在该过程中，可以在该过程中``计算'''``释放''而无需留下痕迹。我们在可流产对象上的初步工作表明，可流产的对象与普通物体固有不同，需要自行研究。我们建议继续这项工作，以更好地理解可流产的对象，并将其与普通对象（即，不可存放）对象进行比较。 可以在具有其他属性的系统中解决具有故障的完全异步系统中无法解决的几个基本问​​题，例如部分同步，失败检测和公平调度程序。最近的研究表明，其中许多系统密切相关（例如，已证明几个失败探测器等同于公平的调度程序），但是要更好地了解它们的相似性和差异仍有许多工作要做。我们将继续调查和比较这些系统，以统一和更好地了解该地区的许多模型和结果。 在许多分布式系统中，一些强大的假设，例如，过程是同步并且不会崩溃的，可以持续长时间。此外，做出如此强大假设的算法可能非常有效，但是在违反这些假设时，它们可能会在相对罕见的情况下失败。为了利用这一点，人们可以首先运行一种非常有效的``主要''算法，因为它依赖于强有力的假设，然后在极少数情况下，当主要算法失败时，依靠较小的``备份''算法而依赖较弱的假设；这是``投机计算''的基本思想。在基于这种方法的初步工作中，我们得出了针对过程崩溃失败的系统中共识的基本问题的投机算法。我们建议将这项初始工作扩展和推广到多个方向，例如解决共识以外的其他问题，以容忍不仅仅是崩溃失败，并根据投机计算进行有效实现共享对象的有效实现。