A characterization of eventual Byzantine agreement

Joseph Y. Halpern, Yoram Moses, Orli Waarts

1990 · 32 citations · 12 references

DOIFull text

Open access

Concepts

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 nonfaulty 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.

References

12