On failure detection, leader election and abstruction-freedom

我们将研究故障检测和leader选举，以及无等待、无阻塞或无阻塞的共享对象的实现，我们将在下面简要解释。故障检测器作为容错分布式计算的基本工具被研究团体广泛使用。我们将继续研究各种类型的故障检测器的规范、实现和使用，以解决异步和部分同步系统中的不同问题，包括消息传递和共享内存计算模型。我们将首先关注onOmega，它是一个故障检测器，可以被认为是（最终的）领导者选举器。特别是，我们将寻求(a)为Omega开发稳定、消息高效且在弱系统假设下的动态环境中工作的算法，(b)推导相应的下界（例如，确定支持Omega实现的系统同步和故障方面的最弱假设），以及(c)实现、实验评估和比较几种实用的Omega算法；这将在我们的分布式系统实验室中完成，最好的算法将集成在一个通用的故障检测器服务包中，该服务包将供公众下载。在共享内存模型中，我们将研究一个相对较新的概念，即障碍自由，以及它与两个更强的进度要求，锁自由和等待自由的关系。作为这项工作的一部分，我们想要确定支持无阻碍的“最弱”同步原语，以及是否可以实现无阻碍的“无仲裁者”。我们的初步调查表明，可以通过一个比安全寄存器弱的寄存器（称为可中止寄存器）来实现无障碍，我们想确定可中止寄存器在某种意义上是否“最小”，以及它们是否无仲裁者。我们还打算调查以下问题：将无阻塞实现转换为无阻塞或无等待实现有多“困难”（根据系统假设）？

We will work on failure detection and leader election, and on implementations of shared objects thatare wait-free, non-blocking, or obstruction-free, as we briefly explain below.Failure detectors are extensively used by the research community as a fundamental tool for fault-tolerantdistributed computing. We will continue our work on the specification, implementation, and use ofvarious types of failure detectors for solving different problems in asynchronous and partially synchronoussystems, in both the message-passing and shared-memory models of computation. We will initially focus onOmega, a failure detector that can be considered an (eventual) leader elector. In particular, we will seek to(a) develop algorithms for Omega that are stable, message-efficient, and work in dynamic environmentsunder weak system assumptions, (b) derive corresponding lower bounds (e.g., determine the weakestassumptions, in terms of system synchrony and failures, that support the implementation of Omega), and(c) implement, experimentally evaluate and compare several practical algorithms for Omega; this will be donein our distributed system lab and the best algorithms will be integrated in a general failure detector servicepackage that will be available for public download.In the shared-memory model, we will investigate a relatively recent concept, namely obstruction-freedom,and its relation to two stronger progress requirements, lock-freedom and wait-freedom. As part of this work,we would like to determine the ``weakest'' synchronization primitive that supports obstruction-freedom, andwhether obstruction-freedom can be achieved ``arbiter-free''. Our initial investigation shows that obstruction-freedom can be achieved with a register (called abortable register) that is weaker than safe registers, and wewant to determine whether abortable registers are in some sense ``minimal'' and whether they are arbiter-free.We also intend to investigate the following question: How ``hard'' is it (in terms of system assumptions)to transform obstruction-free implementations into non-blocking or wait-free ones?