Algorithms, abstractions and models for 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.