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.