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

Personal Author(s) : Michel, Ruben

PDF Url : ADA191256

Report Date : Jan 1988

Pagination or Media Count : 65

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.

Descriptors :   *INFORMATION THEORY, MESSAGE PROCESSING, THEOREMS, MULTIPROCESSORS

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE