Participant-Restricted Consensus in Asynchronous Crash-Prone Read/Write Systems and Its Weakest Failure Detector

摘要

A failure detector is a device (object) that provides the processes with information on failures. Failure detectors were introduced to enrich asynchronous systems so that it becomes possible to solve problems (or implement concurrent objects) that are otherwise impossible to solve in pure asynchronous systems where processes are prone to crash failures. The most famous failure detector (which is called 'eventual leader' and denoted Ω is the weakest failure detector which allows consensus to be solved in n-process asynchronous systems where up to t = n — 1 processes may crash in the read/write communication model, and up to t < n/2 processes may crash in the message-passing communication model. In these models, all correct processes are supposed to participate in a consensus instance and in particular the eventual leader. This paper considers the case where some subset of processes that do not crash (not predefined in advance) are allowed not to participate in a consensus instance. In this context J? cannot be used to solve consensus as it could elect as eventual leader a non-participating process. This paper presents the weakest failure detector that allows correct processes not to participate in a consensus instance.This failure detector, denoted Ω*, is a variant of Ω. The paper presents also an Ω*-based consensus algorithm for the asynchronous read/write model, in which any number of processes may crash, and not all the correct processes are required to participate.