Characterization of eventual Byzantine agreement

Abstract

We investigate eventual Byzantine agreement (EBA) in the crash and omission failure models. The emphasis is on characterizing optimal EBA protocols in terms of the states of knowledge required by the processors in order to attain EBA. It is well known that common knowledge among the non-faulty processors is a necessary and sufficient condition for attaining simultaneous Byzantine agreement (SBA). We define a new variant of common knowledge, which we call continual common knowledge, in terms of which we can characterize necessary and sufficient conditions for attaining EBA. Using our characterization, we provide a technique that allows us to start with any EBA protocol, apply a certain construction twice, and arrive at an optimal EBA protocol.