A simple and fast asynchronous consensus protocol based on a weak failure detector |
| |
Authors: | Michel Hurfin Michel Raynal |
| |
Affiliation: | (1) IRISA, Campus de Beaulieu, F-35042 Rennes Cedex, France (e-mail: {hurfin, raynal}@irisa.fr) , FR |
| |
Abstract: | Summary. The Consensus problem is a fundamental paradigm for fault-tolerant asynchronous systems. It abstracts a family of problems
known as Agreement (or Coordination) problems. Any solution to consensus can serve as a basic building block for solving such
problems (e.g., atomic commitment or atomic broadcast). Solving consensus in an asynchronous system is not a trivial task: it has been proven
(1985) by Fischer, Lynch and Paterson that there is no deterministic solution in asynchronous systems which are subject to
even a single crash failure. To circumvent this impossibility result, Chandra and Toueg have introduced the concept of unreliable
failure detectors (1991), and have studied how these failure detectors can be used to solve consensus in asynchronous systems
with crash failures. This paper presents a new consensus protocol that uses a failure detector of the class . Like previous protocols, it is based on the rotating coordinator paradigm and proceeds in asynchronous rounds. Simplicity
and efficiency are the main characteristics of this protocol. From a performance point of view, the protocol is particularly
efficient when, whether failures occur or not, the underlying failure detector makes no mistake (a common case in practice).
From a design point of view, the protocol is based on the combination of three simple mechanisms: a voting mechanism, a small
finite state automaton which manages the behavior of each process, and the possibility for a process to change its mind during
a round.
Received: August 1997 / Accepted: March 1999 |
| |
Keywords: | :Asynchronous distributed systems – Consensus problem – Crash failures – Fault-tolerance – Unreliable failure detectors |
本文献已被 SpringerLink 等数据库收录! |
|