Algorithms, abstractions and models for distributed computing.

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

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

我们计划致力于分布式计算中的基本问题、抽象和模型。这项研究将包括消息传递模型（适用于地理上分布式的系统，如点对点、移动的或云系统）和共享内存模型（适用于多核系统）。一个目标是获得更好的算法和抽象，简化设计或提高分布式系统的性能。另一个目标是比较，并在可能的情况下统一，在这一领域的许多模型和相关的结果。我们现在简要总结为实现这些目标而提出的一些工作。可线性化的无等待共享对象是构建异步共享内存分布式系统的一个强大的抽象：它们的行为就像它们被顺序访问一样，每个调用无等待对象操作的非故障进程都保证得到响应，即使其他进程很慢或崩溃。然而，实现这样的对象可能是困难和低效的，这导致了对语义较弱（尽管仍然有用）但实现更容易和更有效的对象的研究。本着这一精神，我们建议继续研究可中止物体，即，相互干扰的操作可能会中止而不生效的对象。这让人想起事务内存、数据库事务和可中止互斥的简单而有吸引力的行为-在这些技术中，一个进程可以在争用的情况下"保释“计算而不留下痕迹。我们对可中止对象的初步研究表明，可中止对象与普通对象有着本质的不同，需要对其进行单独研究。我们建议继续这项工作，以更好地理解可中止对象，并将它们与普通对象（即，不可中止的）对象。在完全异步的故障系统中无法解决的几个基本问题可以在具有附加属性的系统中解决，例如部分同步，故障检测和公平分配器。最近的研究表明，许多这些系统是密切相关的（例如，几种故障检测器已被证明等同于公平检测器），但仍需要做大量的工作来更好地理解它们的相似性和差异。我们将继续研究和比较这些系统，以统一和更好地理解该领域的许多模型和结果。在许多分布式系统中，一些强有力的假设，例如，进程是同步的，不会崩溃，可以保持相对较长的时间。此外，做出这种强假设的算法可能非常有效，但当这些假设被违反时，它们可能会在相对罕见的情况下失败。为了利用这一点，可以首先运行一个非常有效的“主”算法，因为它依赖于强假设，然后，在主算法失败的极少数情况下，依靠依赖于较弱假设的效率较低的“备份”算法;这是“推测计算”的基本思想。在基于这种方法的初步工作中，我们推导出了针对具有进程崩溃故障的系统中共识基本问题的推测性算法。我们建议在几个方向上扩展和推广这一初步工作，例如解决共识以外的问题，容忍不仅仅是崩溃故障，并调查基于推测计算的共享对象的有效实现。