Efficient Protocols for Attaining Common Knowledge and Simultaneous Byzantine Agreement.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1988
Accession Number
ADA191256

Entities

People

  • Ruben Michel

Organizations

  • Yale University

Tags

Communities of Interest

  • Biomedical
  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Agreements
  • Algorithms
  • Coding
  • Computer Programming
  • Computer Science
  • Computers
  • Consistency
  • Construction
  • Decoding
  • Finite Alphabet
  • Military Research
  • Notation
  • Numbers
  • Polynomials
  • Sequences
  • Standards
  • Theorems

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Systems Analysis and Design