Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults

Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if n > 2f for f Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if n > 3f+2k for f Byzantine faults and k crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to f Byzantine faults and k crash faults if n > 2f+k. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that n > 2f+k is optimally resilient for consensus and state machine replication protocols.