A Unified Proof of Minimum Time Complexity for Reaching Consensus and Uniform Consensus -- An Oracle-based Approach
In this paper, we offer simple and intuitive proofs to two lower bound results in distributed computing: a minimum of n + 1 and n + 2 rounds for reaching consensus and uniform consensus respectively when at most n faults can happen. Both proofs are based on a novel oracle argument. These two induction proofs are unified in the following sense: the induction steps are the same and only the initial step (n=0) needs to be proved separately. The techniques used in the proof offer new insights into the lower bound results in distributed computing.