Algorithms, abstractions and models for distributed computing.

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

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

我们计划研究分布式计算中的基本问题、抽象和模型。这项研究将包括消息传递模型（适用于地理上分布的系统，如点对点、移动或云系统）和共享内存模型（适用于多核系统）。其中一个目标是推导出更好的算法和抽象，以简化分布式系统的设计或提高其性能。另一个目标是比较，并在可能的情况下统一该领域的一些模型和相关结果。我们现在简要地总结一下为实现这些目标而提出的一些工作。