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