1990 · 32 citations · 12 references
ComputingComputer ScienceComputer SystemsFault ToleranceFault-tolerant ComputingFault-tolerant SystemsFault-tolerant CommunicationReliable Distributed SystemsAgreement ProtocolsByzantine AgreementCrash Recovery ProtocolsFailure ModesTwo-step Verification
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.
12
Reaching Agreement in the Presence of Faults
Marshall C. Pease, Robert E. Shostak, Leslie Lamport · Journal of the ACM · 1980 · 2.4K citations · Full text
Knowledge and common knowledge in a distributed environment
Joseph Y. Halpern, Yoram Moses · 1984 · 287 citations · Full text
Modelling knowledge and action in distributed systems
Joseph Y. Halpern, Ronald Fagin · Distributed Computing · 1989 · 158 citations