Paper 2002/085

Efficient and Player-Optimal Strong Consensus

Matthias Fitzi and Juan A. Garay

Abstract

In the {\em strong consensus} problem, $n$ players attempt to reach agreement on a value initially held by {\em one of the good players}, despite the (malicious) behavior of up to $t$ of them. Although the problem is closely related to the standard consensus problem (aka Byzantine agreement), the only known solution with the optimal number of players requires exponential computation and communication in the unconditional setting. In this paper we study this problem, and present {\em efficient} protocols and tight lower bounds for several standard distributed computation models --- unconditional, computational, synchronous, and asynchronous.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
garay @ research bell-labs com
History
2002-06-30: received
Short URL
https://ia.cr/2002/085
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/085,
      author = {Matthias Fitzi and Juan A.  Garay},
      title = {Efficient and Player-Optimal Strong Consensus},
      howpublished = {Cryptology ePrint Archive, Paper 2002/085},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/085}},
      url = {https://eprint.iacr.org/2002/085}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.