Page 1 of 9Free preview · 1–5

About this document

This paper proves that deterministic consensus in a completely asynchronous distributed system cannot guarantee termination when even one process may crash, despite reliable message delivery. The proof uses bivalent configurations to construct an admissible execution in which no decision is reached. It also presents a consensus protocol for the restricted case where a strict majority of processes are initially alive and none fail during execution. Published in the Journal of the Association for Computing Machinery, volume 32, number 2, April 1985, pages 374 - 382.

Free preview text

The first 5 pages, shown as text so search engines and readers can find this document.

Page 1

Impossibility of Distributed Consensus with One Faulty Process MICHAEL J. FISCHER Yale University, New Haven, Connecticut NANCY A. LYNCH Massachusetts Institute of Technology, Cambridge, Massachusetts AND MICHAEL S. PATERSON University of Warwick, Coventry, England Abstract. The consensusproblem involves an asynchronous system of processes,some of which may be unreliable. The problem is for the reliable processesto agree on a binary value. In this paper, it is shown 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. Categories and Subject Descriptors: C.2.2 [Computer-Communication Networks]: Network Protocols- protocol architecture; C.2.4 [Computer-Communication Networks]: Distributed Systems-distributed applications; distributed databases; network operating systems; C.4 [Performance of Systems]: Reliabil- ity, Availability, and Serviceability; F. 1.2 [Computation by Abstract Devices]: Modes of Computation- parallelism; H.2.4 [Database Management]: Systems-distributed systems; transaction processing General Terms: Algorithms, Reliability, Theory Additional Key Words and Phrases: Agreement problem, asynchronous system, Byzantine Generals problem, commit problem, consensus problem, distributed computing, fault tolerance, impossibility proof, reliability I. Introduction The problem of reaching agreement among remote processesis one of the most fundamental problems in distributed computing and is at the core of many Editing of this paper was performed by guest editor S. L. Graham. The Editor-in-Chief of JACM did not participate in the processing of the paper. This work was supported in part by the OBice of Naval Research under Contract NO00 14-82-K-O154, by the Office of Army Research under Contract DAAG29-79-C-0155, and by the National Science Foundation under Grants MCS-7924370 and MCS-8 116678. This work was originally presented at the 2nd ACM Symposium on Principles of Database Systems, March 1983. Authors’ present addresses:M. J. Fischer, Department of Computer Science, Yale University, P.O. Box 2 158, Yale Station, New Haven, CT 06520; N. A. Lynch, Laboratory for Computer Science, Massachu- setts Institute of Technology, 545 Technology Square, Cambridge, MA 02 139; M. S. Paterson, Depart- ment of Computer Science, University of Warwick, Coventry CV4 7AL, England Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1985 ACM 0004-541 l/85/0400-0374 $00.75 Journal of the Assccktion for Computing Machinery, Vol. 32, No. 2, April 1985, pp. 374-382.

Page 2

Impossibility of Distributed Consensuswith One Faulty Process 375 algorithms for distributed data processing, distributed file management, and fault- tolerant distributed applications. A well-known form of the problem is the “transaction commit problem,” which arises in distributed database systems [6, 13, 15-17, 21-241 (see also G. LeLann, private communication, quoted in [ 151). The problem is for all the data manager processes that have participated in the processing of a particular transaction to agree on whether to install the transaction’s results in the database or to discard them. The latter action might be necessary, for example, if some data managers were, for any reason, unable to carry out the required transaction processing. Whatever decision is made, all data managers must make the same decision in order to preserve the consistency of the database. Reaching the type of agreement needed for the “commit” problem is straightfor- ward if the participating processesand the network are completely reliable. How- ever, real systems are subject to a number of possible faults, such as process crashes, network partitioning, and lost, distorted, or duplicated messages.One can even consider more Byzantine types of failure [5, 7, 8, 11, 14, 18, 191 in which faulty processesmight go completely haywire, perhaps even sending messagesaccording to some malevolent plan. One therefore wants an agreement protocol that is as reliable as possible in the presence of such faults. Of course, any protocol can be overwhelmed by faults that are too frequent or too severe, so the best that one can hope for is a protocol that is tolerant to a prescribed number of “expected” faults. In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the messagesystem is reliable- it delivers all messagescorrectly and exactly once. Nevertheless, even with these assumptions, the stopping of a single process at an inopportune time can cause any distributed commit protocol to fail to reach agreement. Thus, this important problem has no robust solution without further assumptions about the computing environment or still greater restrictions on the kind of failures to be tolerated! Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processes or about the delay time in delivering a message.We also assume that processesdo not have accessto synchronized clocks, so algorithms based on time-outs, for example, cannot be used. (In particular, the solutions in [6] are not applicable.) Finally, we do not postulate the ability to detect the death of a process, so it is impossible for one process to tell whether another has died (stopped entirely) or is just running very slowly. Our impossibility result applies to even a very weak form of the consensus problem. Assume that every process starts with an initial value in (0, 11.A nonfaulty process decides on a value in (0, 1) by entering an appropriate decision state. All nonfaulty processesthat make a decision are required to choose the same value. For the purpose of the impossibility proof, we require only that some process eventually make a decision. (Of course, any algorithm of interest would require that all nonfaulty processesmake a decision.) The trivial solution in which, say, 0 is always chosen is ruled out by stipulating that both 0 and 1 are possible decision values, although perhaps for different initial conligurations. Our system model is rather strong so as to make our impossibility proof as widely applicable as possible. Processesare modeled as automata (with possibly infinitely many states) that communicate by means of messages.In one atomic step, a process can attempt to receive a message, perform local computation on the basis of

Page 3

376 M. J. FISCHER, N. A. LYNCH, AND M. S. PATERSON whether or not a messagewas delivered to it (and if so, which one), and send an arbitrary but finite set of messagesto other processes.In particular, an “atomic broadcast” capability is assumed,so a processcan send the same messagein one step to all other processeswith the knowledge that if any nonfaulty processreceives the message,then all the nonfaulty processeswill. Every messageis eventually delivered as long as the destination process makes infinitely many attempts to receive,but messagescan be delayed, arbitrarily long, and delivered out of order. The asynchronous commit protocols in current use all seemto have a “window of vulnerability”- an interval of time during the execution of the algorithm in which the delay or inaccessibility of a single processcan causethe entire algorithm to wait indefinitely. It follows from our impossibility result that every commit protocol has such a “window,” confirming a widely believed tenet in the folklore. 2. Consensus Protocols A consensus protocol P is an asynchronous system of N processes(N I 2). Each processp has a one-bit input register x,, an output register yp with values in (b, 0, 11,and an unbounded amount of internal storage. The values in the input and output registers, together with the program counter and internal storage, comprise the internal state. Initial states prescribe fixed starting values for all but the input register; in particular, the output register starts with value b. The states in which the output register has value 0 or 1 are distinguished as being decision states. p acts deterministically according to a transition function. The transition function cannot change the value of the output register once the process has reached a decision state; that is, the output register is “write-once.” The entire systemP is specifiedby the transition functions associatedwith eachof the processes and the initial values of the input registers. Processescommunicate by sending each other messages.A message is a pair (p, m), where p is the name of the destination processand m is a “messagevalue” from a fixed universe M. The message system maintains a multiset, called the message buffer, of messagesthat have been sent but not yet delivered. It supports two abstract operations: send(p, m): Places(p, m) in the messagebuffer; receive(p): Deletes some message(p, m) from the buffer and returns m, in which casewe say (p, m) is delivered, or returns the special null marker 0 and leavesthe buffer unchanged. Thus, the messagesystem acts nondeterministically, subject only to the condition that if receive(p) is performed infinitely many times, then every message(p, m) in the messagebuffer is eventually delivered. In particular, the messagesystem is allowed to return 0 a finite number of times in responseto receive(p), even though a message(p, m) is present in the buffer. A configuration of the system consists of the internal state of each process, together with the contents of the messagebuffer. An initial configuration is one in which each processstarts at an initial state and the messagebuffer is empty. A step takes one configuration to another and consists of a primitive step by a single processp. Let C be a configuration. The step occurs in two phases.First, receive(p) is performed on the messagebuffer in C to obtain a value m E M u (0). Then, depending on p’s internal state in C and on m, p enters a new internal state and sends a finite set of messagesto other processes.Since processesare deterministic, the step is completely determined by the pair e = (p, m), which we

Page 4

-Impossibility of Distributed Consensus with One Faulty Process 377 FIGURE1 call an event. (This “event” should be thought of as the receipt of m by p.) e(C) denotes the resulting configuration, and we say that e can be applied to C. Note that the event (p, 0) can always be applied to C, so it is always possible for a process to take another step. A schedule from C is a finite or infinite sequence u of events that can be applied, in turn, starting from C. The associated sequence of steps is called a run. If u is finite, we let a(C) denote the resulting configuration, which is said to be reachable from C. A configuration reachable from some initial configuration is said to be accessible. Hereafter, all configurations mentioned are assumed to be accessible. The following lemma expressesa “commutativity” property of schedules. LEMMA 1. Suppose that from some configuration C, the schedules ul, (~2lead to configurations C1, C2, respectively. If the sets of processes taking steps in c1 and 02, respectively, are disjoint, then u2 can be applied to Cl and (~1can be applied to C2, and both lead to the same configuration C,. (See Figure 1.) PROOF. The result follows at once from the system definition, since u1 and u2 do not interact. Cl A configuration C has decision value v if some process p is in a decision state with y,, = v. A consensus protocol is partially correct if it satisfies two conditions: (1) No accessible configuration has more than one decision value. (2) For each v E (0, I), some accessible configuration has decision value v. A processp is nonfaulty in a run provided that it takes infinitely many steps, and it is faulty otherwise. A run is admissible provided that at most one process is faulty and that all messagessent to nonfaulty processesare eventually received. A run is a deciding run provided that some process reaches a decision state in that run. A consensus protocol P is totally correct in spite of onefault if it is partially correct, and every admissible run is a deciding run. Our main theorem shows that every partially correct protocol for the consensus problem has some admissible run that is not a deciding run. 3. Main Result THEOREM 1. No consensusprotocol is totally correct in spite of onefault. PROOF. Assume to the contrary that P is a consensus protocol that is totally correct in spite of one fault. We prove a sequence of lemmas which eventually lead to a contradiction.

Page 5

378 M. J. FISCHER, N. A. LYNCH, AND M. S. PATERSON The basic idea is to show circumstances under which the protocol remains forever indecisive. This involves two steps. First, we argue that there is some initial configuration in which the decision is not already predetermined. Second, we construct an admissible run that avoids ever taking a step that would commit the system to a particular decision. Let C be a configuration and let V be the set of decision values of configurations reachable from C. C is bivalent if 11/l = 2. C is univalent if 1VI = 1, let us say 0-valent or I-valent according to the corresponding decision value. By the total correctness of P, and the fact that there are always admissible runs, Vf 0. Cl LEMMA 2. P has a bivalent initial configuration. PROOF. Assume not. Then P must have both 0-valent and 1-valent initial configurations by the assumed partial correctness. Let us call two initial configu- rations adjacent if they differ only in the initial value x, of a single process p. Any two initial configurations are joined by a chain of initial configurations, each adjacent to the next. Hence, there must exist a 0-valent initial configuration CO adjacent to a 1-valent initial configuration Ci. Let p be the process in whose initial value they differ. Now consider some admissible deciding run from COin which process p takes no steps, and let u be the associated schedule. Then u can be applied to C, also, and corresponding configurations in the two runs are identical except for the internal state of process p. It is easily shown that both runs eventually reach the same decision value. If the value is 1, then Co is bivalent; otherwise, Ci is bivalent. Either case contradicts the assumed nonexistence of a bivalent initial configura- tion. Cl LEMMA 3. Let C be a bivalent configuration of P, and let e = (p, m) be an event that is applicable to C. Let %?be the set of configurations reachablefrom C without applying e, and let 9 = e(g) = (e(E) I E E %?and e is applicable to E). Then, 9 contains a bivalent configuration. PROOF. Since e is applicable to C, then by definition of ‘Z and the fact that messagescan be delayed arbitrarily, e is applicable to every E E %?7. Now assume that 9 contains no bivalent configurations, so every configuration D E 9 is univalent. We proceed to derive a contradiction. Let Ei be an i-valent configuration reachable from C, i = 0, 1. (Ei exists since C is bivalent.) If Ei E %Y’,let Fi = e(Ei) E g. Otherwise, e was applied in reaching Ei, and so there exists Fi E .9 from which Ei is reachable. In either case, Fi is i-valent since Fi is not bivalent (since Fi E B and 5& contains no bivalent configurations) and one of Ei and Fi is reachable from the other. Since Fi E 9, i = 0, 1, B contains both 0-valent and 1-valent configurations. Call two configurations neighbors if one results from the other in a single step. By an easy induction, there exist neighbors Co, Ci E %5’such that Di = e(Ci) is i-valent, i = 0, 1. Without loss of generality, C, = e’(Co) where e’ = (p’, m’). Case 1. Ifp’ # p, then D1 = e’(&,) by Lemma 1. This is impossible, since any successorof a 0-valent configuration is 0-valent. (See Figure 2.) Case 2. If p’ = p, then consider any finite deciding run from Co in which p takes no steps. Let u be the corresponding schedule, and let A = a(C,,). By Lemma 1, u is applicable to Di, and it leads to an i-valent configuration Ei = a(Di), i = 0, 1. Also

Tags

Doxxly editorial guide

Impossibility of Distributed Consensus with One Faulty Process: summary, contents and background

This guide helps you understand the scope of Impossibility of Distributed Consensus with One Faulty Process before or alongside reading the original document. It is based on the catalogue record, credited creator, source, classification and topics shown on this page. It does not replace the original work and does not invent claims about passages that Doxxly cannot verify.

Summary and overview

Impossibility of Distributed Consensus with One Faulty Process is a 9-page documentcredited to Kaya U. Whitlock. This paper proves that deterministic consensus in a completely asynchronous distributed system cannot guarantee termination when even one process may crash, despite reliable message delivery. The proof uses bivalent configurations to construct an admissible execution in which no decision is reached. It also presents a consensus protocol for the restricted case where a strict majority of processes are initially alive and none fail during execution. Published in the Journal of the Association for Computing Machinery, volume 32, number 2, April 1985, pages 374 - 382. It appears in the Science & Engineering collection, which groups it with other material that readers may use for comparison and further study.

The item can be approached in several ways. A reader looking for a quick orientation can begin with the free five-page preview, inspect the page structure and use the metadata to judge relevance. Someone undertaking deeper research can work through the complete file, search its indexed text, record useful page references and compare its treatment of Distributed computing, Consensus, Asynchronous systems, Fault tolerance, Impossibility proofs, Transaction commit, Algorithms with the related resources linked below.

Rather than reducing the work to a single claim, this page treats it as a source that should be read in context. The title, creator, publication source, licence and format all help explain what kind of evidence it may offer. Readers should distinguish the original author's statements from Doxxly's catalogue description, and should cite the original edition when using the material in academic, professional or published work.

Key topics and reader takeaways

The catalogue connects this document with Distributed computing, Consensus, Asynchronous systems, Fault tolerance, Impossibility proofs, Transaction commit, Algorithms. These terms offer practical entry points rather than a substitute for close reading. Start by identifying the definitions, examples, arguments, tables or visual explanations attached to each topic. Then note where the creator draws connections, makes distinctions or moves from background material to a conclusion, recommendation, calculation or narrative development.

A useful reading method is to separate description from interpretation. First record what the item actually presents: names, headings, figures, formulas, quotations or stated propositions. Next consider why those details matter within the whole work. Finally compare them with another source from the same subject area. This process helps turn a long digital file into evidence that can be evaluated rather than merely skimmed.

Table of contents and reading guide

The following is an editorial content guide based on the verified catalogue topics. It is not represented as the original author's formal table of contents. Use it to organise notes while moving through the 9 pages in the player.

  1. Part 1

    Distributed computing

    Use this section of the reading guide to identify how Distributed computing appears in Impossibility of Distributed Consensus with One Faulty Process, note important terms, and connect the subject to the wider purpose of the work.

  2. Part 2

    Consensus

    Use this section of the reading guide to identify how Consensus appears in Impossibility of Distributed Consensus with One Faulty Process, note important terms, and connect the subject to the wider purpose of the work.

  3. Part 3

    Asynchronous systems

    Use this section of the reading guide to identify how Asynchronous systems appears in Impossibility of Distributed Consensus with One Faulty Process, note important terms, and connect the subject to the wider purpose of the work.

  4. Part 4

    Fault tolerance

    Use this section of the reading guide to identify how Fault tolerance appears in Impossibility of Distributed Consensus with One Faulty Process, note important terms, and connect the subject to the wider purpose of the work.

  5. Part 5

    Impossibility proofs

    Use this section of the reading guide to identify how Impossibility proofs appears in Impossibility of Distributed Consensus with One Faulty Process, note important terms, and connect the subject to the wider purpose of the work.

  6. Part 6

    Transaction commit

    Use this section of the reading guide to identify how Transaction commit appears in Impossibility of Distributed Consensus with One Faulty Process, note important terms, and connect the subject to the wider purpose of the work.

  7. Part 7

    Algorithms

    Use this section of the reading guide to identify how Algorithms appears in Impossibility of Distributed Consensus with One Faulty Process, note important terms, and connect the subject to the wider purpose of the work.

When a heading in the original differs from this guide, follow the original heading in your citation. Page numbers can also vary between editions. Doxxly's direct page field is useful for navigation, but formal references should include the title, creator, source and edition details available in the file itself.

About Kaya U. Whitlock

Doxxly credits Kaya U. Whitlock as the author or creator of Impossibility of Distributed Consensus with One Faulty Process. This page does not add an unverified biography, job title or institutional affiliation. The attribution is preserved so readers can distinguish the creator from the hosting library and follow the original record when an external author link is available.

Author context matters because a work reflects a particular purpose, audience and point of view. Before relying on the material, consider what the creator set out to explain, when the source was produced and whether later research or revised guidance should also be consulted. For literature and philosophy, compare translations and editions; for technical material, check whether a newer version has superseded the one shown here.

About the source organisation

The recorded source for this item is groups.csail.mit.edu. Doxxly provides access and discovery tools but does not claim to be the original publisher unless explicitly stated. Source links, creator attribution and the recorded Publicly available file collected for editorial review licence are displayed to help readers assess provenance and permitted use.

Provenance is especially important for reports, standards, presentations and working spreadsheets. Check the original source for amendments, supporting files and current policy. A trustworthy research workflow keeps the source URL with any notes or downloaded copy, verifies important figures against the original, and avoids treating an archived document as automatically current.

Visit groups.csail.mit.edu

How to read and use this document

Begin with the title and opening pages, then use the guide above to decide whether to read sequentially or move to a particular topic. The Doxxly player provides previous and next navigation, a direct page field, zoom steps, fit-to-width and fit-to-page modes, rotation and fullscreen. These controls are useful when a page contains small type, a wide table, an image, a scanned layout or a dense sequence of notes.

The first five pages are open to every visitor. A plan unlocks the complete item and full-document search. Search is best used for distinctive names, technical terms or short phrases; broad words can produce too many possible contexts. When you find a useful passage, read the surrounding pages so that a sentence, chart or formula is not separated from its explanation.

If downloading is enabled, members can obtain the original PDF file. Keep the original format when formulas, slide sequencing, pagination or layout carries meaning. Respect the Publicly available file collected for editorial review terms displayed on this page, and use the rights-report link if you believe the attribution or availability needs review.

Research questions to consider

As you read Impossibility of Distributed Consensus with One Faulty Process, ask which audience the creator addresses, what problem or idea organises the work, what evidence is presented, and which assumptions remain unstated. Note whether important terms are defined consistently and whether examples represent a broader pattern or a narrow case. For quantitative material, record units, time periods, formulas and data sources. For interpretive material, separate the creator's language from your own summary.

A second set of questions concerns relevance today. Which parts remain durable, which depend on their historical or institutional setting, and what would need confirmation from a newer source? Following the tags and the Science & Engineering collection can reveal useful comparisons. Agreement between sources can strengthen confidence, while disagreement can point to changing definitions, methods, evidence or priorities.

Finally, decide what you need from the item: background knowledge, a quotation, a worked example, a model, a visual explanation or a starting bibliography. That purpose should guide the depth of reading and the notes you keep. Doxxly helps locate and navigate the source; careful interpretation remains the reader's responsibility.

Explore more Science & Engineering resources

Frequently asked questions about Impossibility of Distributed Consensus with One Faulty Process

Practical answers about reading, downloading and understanding this document on Doxxly.

More in Science & Engineering