DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA191256
Title:
Efficient Protocols for Attaining Common Knowledge and Simultaneous Byzantine Agreement.
Descriptive Note:
Technical rept.,
Corporate Author:
YALE UNIV NEW HAVEN CONN DEPT OF CHEMISTRY
Report Date:
1988-01-01
Pagination or Media Count:
65.0
Abstract:
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.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE
