# Quorum Systems Made Practical

## Definitions

**read fault tolerance** - largest number *f* such that read quorum still available

**Quorum system** is *Q = (RW)*, where *R* is the set of read quorums,
  and *W* the set of write quorums.

**Strategy** for a quorum system is a pair *sig =
  (sig<sub>R</sub>, sig<sub>W</sub>)*, where *sig<sub>R</sub>* is
  probabilities set of probabilities 0->1 of all read
  quorums.

  Strategy is just the chosen probabilities of each read and write
  quorum, given a pre-defined set of
  read and write quorums.


*load<sub>sigR</sub>(x)* is probability that *x* is chosen by by
 *sig<sub>R</sub>* (i.e. prob that *x* is included in the read quorum
 chosen).

If workload has **read fraction** *f<sub>r</sub>* (fraction of
accesses that are reads), then:

**load on x** is *f<sub>r</sub> x load<sub>sigR</sub>(x) (1 - f<sub>r</sub>) x load<sub>sigW</sub>(x)*

Most heavily loaded node is throughput bottleneck, so the above is the
**load of the strategy**.

**Load of a quorum system** is the minimal load of any strategy over
  that quorum system.

**Capacity** of a quorum system is reciprocal of load.

## Example

![pic](quorums2x3.png)

- With *f<sub>r</sub>* = 1.0, each node *x* has load 0.5, capacity of 2.
- With *f<sub>r</sub>* = 0.0, each node *x* has load 0.33, capacity of 3.
- With *f<sub>r</sub>* = 0.5, each node *x* has load 1 / (0.5 * 0.5 + 0.5 * 0.33), capacity of 12/5 = 2.4.

## Refinements

*Dual* of bool expression *e* is made by swapping **and** for **or**.
- dual(*ab*) = *a* + *b*
- dual(*a(b+c)+de*) = *(a+bc)(d+e)*

*Optimal write quorums* given read quorums is the dual, and vice
 versa.

*Paths quorum* is said to be optimal read quorum set.
- *R* is *ab + de + ace + dcb*
- dual = *(a+b)(d+e)(a+c+e)(d+c+b)*

## Lessons learned
- majority quorums underperform
  - especially w/ heterogenous nodes
![pic](quorumsStacked.png)


- optimal not always optimal
  - optimal in *limit*
  - heterogeneity in nodes and workload


paths: ace + bcd + de + ab

Comments:
- in Python?
