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.

18 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu