Efficient Protocols for Attaining Common Knowledge and Simultaneous Byzantine Agreement.
YALE UNIV NEW HAVEN CONN DEPT OF CHEMISTRY
Pagination or Media Count:
Motivated by recent research in the problems of attaining Common Knowledge and Simultaneous Byzantine Agreement in the crash and omission models, these problems are studied in a more malicious scenario where incorrect processors may transmit arbitrary messages. This paper introduces the notion of common knowledge informative protocols, which are protocols that attain, in a way, maximal common knowledge. After characterizing these protocols we design a common knowledge informative protocol which is maximally communication efficient according to various natural complexity measures. This protocol allows us to derive a worst case exponential lower bound on the number of bits that correct processors transmit in runs of common knowledge informative protocols and in runs of protocols which attain an eager type of Simultaneous Byzantine Agreement.