On failure detection, leader election and abstruction-freedom

点击翻译按钮获取中文摘要

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?