A bivalency proof of the lower bound for uniform consensus
Bivalency argument is a widely-used technique that employs forward induction to show impossibility results and lower bounds related to consensus. However, for a synchronous distributed system of n processes with up to t potential and f actual crash failures, applying bivalency argument to prove the lower bound for reaching uniform consensus is still an open problem. In this paper, we address this problem by presenting a bivalency proof that the lower bound for reaching uniform consensus is (f + 2) -rounds where 0 <= f <= t - 2. (c) 2005 Elsevier B.V. All rights reserved.
uniform consensus bivalency argument synchronous distributed systems distributed computing