Information Processing Letters 71 (1999) 155–158A simple bivalency proof thatt-resilient consensus requires t + 1 rounds✩Marcos Kawazoe Aguilera1, Sam Toueg∗Department of Computer Science, Upson Hall, Cornell University, Ithaca, NY 14853-7501, USAReceived 28 August 1998; received in revised form 1 April 1999Communicated by F.B. SchneiderAbstractWe use a straightforward bivalency argument borrowed from Fischer et al. (1985) to show that in a synchronous system withup to t crash failures solving consensus requires at least t +1 rounds. The proof is simpler and more intuitive than the traditionalone: It uses an easy forward induction rather than a more complex backward induction which needs the induction hypothesisseveral times. 1999 Elsevier Science B.V. All rights reserved.Keywords: Distributed computing; Fault tolerance; Consensus; Lower bound; Synchronous system; Bivalency1. BackgroundA fundamental result of distributed computing isthat solving consensus in a synchronous system withup to t process crashes requires at least t +1 rounds [8,7,4]. The traditional proof of this result proceeds bya rather complex backward induction that uses theinduction hypothesis several times [9]. In this note, weprovide a much simpler and intuitive proof: it uses aneasy forward induction and it is based on a standardbivalency argument. Proofs similar to ours have beenindependently found by Moses and Rajsbaum [10],and by Bar-Joseph and Ben-Or [1] (see Section 3 fordetails on related work).In the following, we consider systems where proces-ses proceed in synchronized rounds: in each round,✩Research partially supported by the NSF grant CCR-9711403and by an Olin Fellowship.∗Corresponding author. Email: [email protected]: [email protected] process sends messages to other processes, re-ceives all the messages sent to it in that round, andchanges state accordingly. When a process crashes ina round, it sends a subset of the messages that it in-tends to send in that round, and does not execute anysubsequent rounds. A correct process is one that nevercrashes.In the consensus problem, every process starts withsome initial value and must make an irrevocabledecision on a value such that:Agreement. No two correct processes decide differ-ently.Validity. If some correct process decides v,thenv isthe initial value of some process.Termination. Every correct process must eventuallydecide some value.0020-0190/99/$ – see front matter  1999 Elsevier Science B.V. All rights reserved.PII:S0020-0190(99)00100-3156 M.K. Aguilera, S. Toueg / Information Processing Letters 71 (1999) 155–1582. The proofWe now show that any consensus algorithm that tol-erates t crashes requires t +1 rounds. Roughly speak-ing, the proof proceeds by contradiction as follows.Suppose there is a consensus algorithm A that toler-ates up to t crashes and always terminates in t rounds.We first show that in any run of A, the configurationat the beginning of round t must be univalent. We thenobtain a contradiction by constructing a run of A thatis bivalent at the beginning of round t . This run is ob-tained by starting from a bivalent initial configurationand extending it one round at a time, while maintain-ing bivalency. Each one-round extension may requirethe killing of a process.Theorem 1. Considera synchronousround-basedsys-tem S with n processes and at most t crash failuressuch that at most one process crashes in each round.If n>t+1 then there is no algorithm that solves con-sensus in t rounds in S .The proof is by contradiction. Suppose there is analgorithm A that solves consensus in t rounds in S .Without loss of generality, we can assume that Ais loquacious, i.e., at every round, each process issupposed to send a message to every process.We consider the configuration of the system S at theend of each round (this is also the configuration of thesystem just before the start of the next round). Such aconfiguration is just the state of each process (whichalso indicates the current round number and whetherit has crashed in a previous round). Informally, aconfiguration C is 0-valent [1-valent] if starting fromC the only possible decisionvalue of correct processesis 0 [1]; C is univalent it is either 0-valent or 1-valent;C is bivalent if it is not univalent.In the following, a k-round partial run rkdenotesan execution of algorithm A up to the end of roundk. Consider the configuration Ckat the end of roundk of partial run rk. We say that rkis 0-valent,1-valent, univalent,orbivalent if Ckis 0-valent, 1-valent, univalent, or bivalent, respectively.We proceed by proving three lemmata. The thirdone contradicts the first and thus completes the proofof the theorem.Lemma 2. Any (t − 1)-round partial run rt−1isunivalent.Proof. The proof is by contradiction.Suppose there isa bivalent (t −1)-round partial run rt−1.Letr0be thet-round run obtained by extending rt−1by one roundsuch that no process crashes in round t. Without lossof generality assume that all correct processes decide0inr0. Since partial run rt−1is bivalent, there is atleast one t-round run r1that extends rt−1such that allcorrect processes decide 1. Note that in round t of r1:(a) exactly one process p must crash (recall that ineach run at most one process crashes per round),and(b) p must fail to send a message to at least onecorrect process, say c.Construct run r0,1which is identical to r1, exceptthat p sends its message to c.Letc0be a process thatdoes not crash in r0,1and is different from c.Suchaprocess must exist since n>t+ 1 implies that thereare at least two correct processes in the system. Notethat:(a) c cannot distinguish between r0,1and r0;(b) c0cannot distinguish between r0,1and r1.By (a), c decides 0 in r0,1, while by (b) c0decides 1in r0,1—a violation of the agreement property ofconsensus. 2Lemma 3. There is a bivalent initial configuration.Proof. (Same as in Fischer et al. [6].) Suppose,for contradiction, that every initial configuration isunivalent. Consider the initial configurations C0andC1such that all processes have initial value 0 and 1,respectively. By the validity property of consensus, C0is 0-valent and C1is 1-valent. Clearly, there are twoinitial configurations that differ by the initial value ofonly one process p, such that one is 0-valent and theother is 1-valent. We can easily reach a contradictionby crashing p at the beginning of round 1 (before itsends any messages to any process). 2Lemma 4. There is a bivalent (t −