Impossibility of distributed consensus with one faulty process

By Michael J. Fischer, Nancy A. Lynch, Mike Paterson. 1983

The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the "Byzantine Generals" problem.

Citations in the corpus

• Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation (2019, neutral): “Compared to traditional Byzantine tolerance in distributed systems (Lynch, 1996; Avizienis et al., 2004; Tanenbaum & Van Steen, 2007; Fischer et al., 1982), Byzantine tolerance in distributed machine learning has unique properties and challenges.”