Team for Research in
Ubiquitous Secure Technology

Citation
Michael Merideth, Michael Reiter. "Probabilistic opaque quorum systems". Distributed Computing: 21st International Symposium, DISC 2007, 403-419, September, 2007.

Abstract
Byzantine-fault-tolerant service protocols like Q/U and FaB Paxos that optimistically order requests can provide increased efficiency and fault scalability. However, these protocols require n ≥ 5b+1 servers (where b is the maximum number of faults tolerated), owing to their use of opaque Byzantine quorum systems; this is 2b more servers than required by some non-optimistic protocols. In this paper, we present a family of probabilistic opaque Byzantine quorum systems that require substantially fewer servers. Our analysis is novel in that it assumes Byzantine clients, anticipating that a faulty client may seek quorums that maximize the probability of error. Using this as motivation, we present an optional, novel protocol that allows probabilistic quorum systems to tolerate Byzantine clients. The protocol requires only one additional round of interaction between the client and the servers, and this round may be amortized over multiple operations. We consider actual error probabilities introduced by the probabilistic approach for concrete configurations of opaque quorum systems, and prove that the probability of error vanishes with as few as n > 3.15b servers as n and b grow.

Electronic downloads

• http://dx.doi.org/10.1007/978-3-540-75142-7_31

• HTML

  Michael Merideth, Michael Reiter. <a
  href="http://www.truststc.org/pubs/374.html"
  >Probabilistic opaque quorum systems</a>,
  Distributed Computing: 21st International Symposium, DISC
  2007, 403-419, September, 2007.

• Plain text

  Michael Merideth, Michael Reiter. "Probabilistic opaque
  quorum systems". Distributed Computing: 21st
  International Symposium, DISC 2007, 403-419, September, 2007.

• BibTeX

  @inproceedings{MeridethReiter07_ProbabilisticOpaqueQuorumSystems,
      author = {Michael Merideth and Michael Reiter},
      title = {Probabilistic opaque quorum systems},
      booktitle = {Distributed Computing: 21st International
                Symposium, DISC 2007},
      pages = {403-419},
      month = {September},
      year = {2007},
      abstract = {Byzantine-fault-tolerant service protocols like
                Q/U and FaB Paxos that optimistically order
                requests can provide increased efficiency and
                fault scalability. However, these protocols
                require n ≥ 5b+1 servers (where b is the maximum
                number of faults tolerated), owing to their use of
                opaque Byzantine quorum systems; this is 2b more
                servers than required by some non-optimistic
                protocols. In this paper, we present a family of
                probabilistic opaque Byzantine quorum systems that
                require substantially fewer servers. Our analysis
                is novel in that it assumes Byzantine clients,
                anticipating that a faulty client may seek quorums
                that maximize the probability of error. Using this
                as motivation, we present an optional, novel
                protocol that allows probabilistic quorum systems
                to tolerate Byzantine clients. The protocol
                requires only one additional round of interaction
                between the client and the servers, and this round
                may be amortized over multiple operations. We
                consider actual error probabilities introduced by
                the probabilistic approach for concrete
                configurations of opaque quorum systems, and prove
                that the probability of error vanishes with as few
                as n > 3.15b servers as n and b grow.},
      URL = {http://www.truststc.org/pubs/374.html}
  }
  

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