Team for Research in
Ubiquitous Secure Technology

Citation
Michael Merideth. "Tradeoffs in Byzantine-Fault-Tolerant State-Machine-Replication Protocol Design". Technical report, Institute for Software Research, Carnegie Mellon University, CMU-ISR-08-110, March, 2008.

Abstract
Many state-machine-replication protocols perform the same tasks of tolerating Byzantine faults and guaranteeing consistency in an asynchronous environment. However, each protocol seems uniquely complex in part because commonalities are lost in descriptions of the protocols. In this paper, we identify Byzantine quorum systems as a unifying factor in the design of each protocol. Leveraging this, we present a framework of high-level, logical phases, which may be optimistic or pessimistic, as a path to understanding: the number of servers required; the number of faults that can be tolerated; and the number of rounds of communication employed by each protocol. Our framework highlights a tradeoff between the number of rounds of communication required and the maximum number of faults that can be tolerated. Furthermore, it highlights an independent tradeoff between an additional round of communication and possibly unnecessary computation. We use the framework to describe three mainstream state-machine-replication protocols and their variants.

Electronic downloads

• HTML

  Michael Merideth. <a
  href="http://www.truststc.org/pubs/382.html"
  ><i>Tradeoffs in Byzantine-Fault-Tolerant
  State-Machine-Replication Protocol
  Design</i></a>, Technical report,  Institute for
  Software Research, Carnegie Mellon University,
  CMU-ISR-08-110, March, 2008.

• Plain text

  Michael Merideth. "Tradeoffs in
  Byzantine-Fault-Tolerant State-Machine-Replication Protocol
  Design". Technical report,  Institute for Software
  Research, Carnegie Mellon University, CMU-ISR-08-110, March,
  2008.

• BibTeX

  @techreport{Merideth08_TradeoffsInByzantineFaultTolerantStateMachineReplication,
      author = {Michael Merideth},
      title = {Tradeoffs in Byzantine-Fault-Tolerant
                State-Machine-Replication Protocol Design},
      institution = {Institute for Software Research, Carnegie Mellon
                University},
      number = {CMU-ISR-08-110},
      month = {March},
      year = {2008},
      abstract = {Many state-machine-replication protocols perform
                the same tasks of tolerating Byzantine faults and
                guaranteeing consistency in an asynchronous
                environment. However, each protocol seems uniquely
                complex in part because commonalities are lost in
                descriptions of the protocols. In this paper, we
                identify Byzantine quorum systems as a unifying
                factor in the design of each protocol. Leveraging
                this, we present a framework of high-level,
                logical phases, which may be optimistic or
                pessimistic, as a path to understanding: the
                number of servers required; the number of faults
                that can be tolerated; and the number of rounds of
                communication employed by each protocol. Our
                framework highlights a tradeoff between the number
                of rounds of communication required and the
                maximum number of faults that can be tolerated.
                Furthermore, it highlights an independent tradeoff
                between an additional round of communication and
                possibly unnecessary computation. We use the
                framework to describe three mainstream
                state-machine-replication protocols and their
                variants.},
      URL = {http://www.truststc.org/pubs/382.html}
  }
  

Posted by Michael Merideth on 28 Apr 2008.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.