The consensus problem in fault-tolerant computing

1 June 1993

journal article
Published by Association for Computing Machinery (ACM) in ACM Computing Surveys

Vol. 25 (2) , 171-220
https://doi.org/10.1145/152610.152612

Abstract

The consensus problem is concerned with the agreement on a system status by the fault-free segment of a processor population in spite of the possible inadvertent or even malicious spread of disinformation by the fault segment of that population. The resulting protocols are useful throughout fault-tolerant distributed systems and will impact the design of other decision systems to come. This paper surveys research on the consensus problem, compares approaches, outlines applications, and suggests directions for future work.

Keywords

This publication has 84 references indexed in Scilit:

Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement
Information and Computation, 1992
Consensus algorithms with one-bit messages
Distributed Computing, 1991
On the reliability of consensus-based fault-tolerant distributed computing systems
ACM Transactions on Computer Systems, 1987
Stopping times of distributed consensus protocols: A probabilistic analysis
Information Processing Letters, 1987
Reliable communication in the presence of failures
ACM Transactions on Computer Systems, 1987
Replication and fault-tolerance in the ISIS system
Published by Association for Computing Machinery (ACM) ,1985
Streets of Byzantium: Network Architectures for Fast Reliable Broadcasts
IEEE Transactions on Software Engineering, 1985
Asynchronous Byzantine consensus
Published by Association for Computing Machinery (ACM) ,1984
On a logical problem
Discrete Mathematics, 1983
A Theory of Diagnosability of Digital Systems
IEEE Transactions on Computers, 1976