Probabilistic Biquorums Conference Paper uri icon

abstract

  • © 2015 IEEE. A biquorum system is a fundamental primitive for designing distributed systems using replicated servers such as distributed storage systems. A traditional biquorum system guarantees a non-Trivial intersection between a write quorum and a read quorum. This strict intersection property is often inconvenient in many practical systems, especially when the communication is done by sending and receiving messages over the possibly unreliable network. Seeking a solution to such systems we study probabilistically cross-intersecting families (probabilistic biquorums) of servers as follows. We develop the theory of the separable selection access strategy: for a write operation w servers are selected (with repetitions allowed) according to a probability distribution p on the set of servers, and for the read operation r servers are selected (with repetitions allowed) according to a probability distribution q on the set of servers. Allowing repetitions in selecting the servers for each operation can greatly simplify the algorithms for the system because one does not need to keep track of which servers have already been selected from the available names. Among other results, we derive the exact intersection probability of the probabilistic biquorum system and a closed form expression for the expected number of servers that are common between the write and the read quorums.

author list (cited authors)

  • Klappenecker, A., & Lee, H.

citation count

  • 0

publication date

  • December 2015

publisher