Impossibility of Distributed Consensus with One Faulty Process

Impossibility of Distributed Consensus with One Faulty Process

April 1985 | MICHAEL J. FISCHER, NANCY A. LYNCH, AND MICHAEL S. PATERSON
This paper presents an impossibility result for achieving consensus in a distributed system with one faulty process. The consensus problem involves processes in an asynchronous system agreeing on a binary value. The authors show that no protocol can guarantee termination in such a scenario, even with only one faulty process. This contrasts with the synchronous case, such as the "Byzantine Generals" problem, where solutions exist. The paper defines a consensus protocol as one where all nonfaulty processes agree on a single value. It proves that in an asynchronous system, where no assumptions are made about process speeds or message delays, and where processes cannot detect failures, it is impossible to ensure that all nonfaulty processes reach a decision. This is because a single process failure can cause the system to enter a state where no decision is made, even if all other processes are functioning correctly. The proof relies on the concept of bivalent configurations, where a configuration allows for both 0 and 1 as possible decision values. The authors show that it is possible to construct an admissible run that avoids making a decision, thus proving the impossibility of a totally correct protocol in the presence of a single fault. The paper also discusses a protocol for solving the consensus problem when a majority of processes are nonfaulty and no process dies during execution. This protocol uses a two-stage process to construct a directed graph and determine a decision based on initial values of processes in an initial clique. The authors conclude that the problem of achieving consensus in a totally asynchronous system cannot be solved, highlighting the need for more refined models of distributed computing that better reflect real-world assumptions about timing and communication.This paper presents an impossibility result for achieving consensus in a distributed system with one faulty process. The consensus problem involves processes in an asynchronous system agreeing on a binary value. The authors show that no protocol can guarantee termination in such a scenario, even with only one faulty process. This contrasts with the synchronous case, such as the "Byzantine Generals" problem, where solutions exist. The paper defines a consensus protocol as one where all nonfaulty processes agree on a single value. It proves that in an asynchronous system, where no assumptions are made about process speeds or message delays, and where processes cannot detect failures, it is impossible to ensure that all nonfaulty processes reach a decision. This is because a single process failure can cause the system to enter a state where no decision is made, even if all other processes are functioning correctly. The proof relies on the concept of bivalent configurations, where a configuration allows for both 0 and 1 as possible decision values. The authors show that it is possible to construct an admissible run that avoids making a decision, thus proving the impossibility of a totally correct protocol in the presence of a single fault. The paper also discusses a protocol for solving the consensus problem when a majority of processes are nonfaulty and no process dies during execution. This protocol uses a two-stage process to construct a directed graph and determine a decision based on initial values of processes in an initial clique. The authors conclude that the problem of achieving consensus in a totally asynchronous system cannot be solved, highlighting the need for more refined models of distributed computing that better reflect real-world assumptions about timing and communication.
Reach us at info@study.space
[slides] Impossibility of distributed consensus with one faulty process | StudySpace