Team for Research in
Ubiquitous Secure Technology

Citation
Michael Merideth, Michael Reiter. "Write markers for probabilistic quorum systems". Technical report, Computer Science Department, Carnegie Mellon University, CMU-CS-07-165, November, 2007.

Abstract
Probabilistic quorum systems can tolerate a larger fraction of faults than can traditional (strict) quorum systems, while guaranteeing consistency with an arbitrarily high probability for a system with enough replicas. However, they are hampered in that, like strict quorum systems, they allow for Byzantine-faulty servers to collude maximally to provide incorrect values to clients. We present a technique based on write markers that prevents faulty servers from colluding unless they are all also selected to be participants in the same update operations. We show that write markers increase the maximum fraction of faults that can be tolerated to b < n/2 from b < n/2.62, where n is the total number of replicas, for probabilistic masking quorum systems (compared with b < n/4 for strict masking quorum systems) and to b < n/2.62 from b < n/3.15 for probabilistic opaque quorum systems (compared with b < n/5 for strict opaque quorum systems). In addition, with write markers, probabilistic masking quorums no longer require write quorums of large or maximal size in order to tolerate the maximum fraction of faults. We describe an implementation of write markers that is effective even if Byzantine clients collude with faulty servers.

Electronic downloads

• http://reports-archive.adm.cs.cmu.edu/anon/2007/abstracts/07-165.html

• HTML

  Michael Merideth, Michael Reiter. <a
  href="http://www.truststc.org/pubs/375.html"
  ><i>Write markers for probabilistic quorum
  systems</i></a>, Technical report,  Computer
  Science Department, Carnegie Mellon University,
  CMU-CS-07-165, November, 2007.

• Plain text

  Michael Merideth, Michael Reiter. "Write markers for
  probabilistic quorum systems". Technical report, 
  Computer Science Department, Carnegie Mellon University,
  CMU-CS-07-165, November, 2007.

• BibTeX

  @techreport{MeridethReiter07_WriteMarkersForProbabilisticQuorumSystems,
      author = {Michael Merideth and Michael Reiter},
      title = {Write markers for probabilistic quorum systems},
      institution = {Computer Science Department, Carnegie Mellon
                University},
      number = {CMU-CS-07-165},
      month = {November},
      year = {2007},
      abstract = {Probabilistic quorum systems can tolerate a larger
                fraction of faults than can traditional (strict)
                quorum systems, while guaranteeing consistency
                with an arbitrarily high probability for a system
                with enough replicas. However, they are hampered
                in that, like strict quorum systems, they allow
                for Byzantine-faulty servers to collude maximally
                to provide incorrect values to clients. We present
                a technique based on write markers that prevents
                faulty servers from colluding unless they are all
                also selected to be participants in the same
                update operations. We show that write markers
                increase the maximum fraction of faults that can
                be tolerated to b < n/2 from b < n/2.62, where n
                is the total number of replicas, for probabilistic
                masking quorum systems (compared with b < n/4 for
                strict masking quorum systems) and to b < n/2.62
                from b < n/3.15 for probabilistic opaque quorum
                systems (compared with b < n/5 for strict opaque
                quorum systems). In addition, with write markers,
                probabilistic masking quorums no longer require
                write quorums of large or maximal size in order to
                tolerate the maximum fraction of faults. We
                describe an implementation of write markers that
                is effective even if Byzantine clients collude
                with faulty servers.},
      URL = {http://www.truststc.org/pubs/375.html}
  }
  

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