最近读到一个有趣的话题：Quorum System的故障概率和负载。

首先是一些概念：

节点集合 $V={v_1, v_2, .., v_n}$

Quorum  $Q\subseteq V$

Quorum System $\cal{S} \subseteq 2^V$，且$Q_1 \cap Q2 \neq \emptyset, \forall Q1,Q2 \in\cal{S}$

故障概率Failure Probability: 假设每个节点故障概率为p，Quorum System  $\cal{S}$的故障概率记为$F_p( \cal{S})$等于每个Quorum都至少有一个节点发生故障的概率。

渐进故障概率Asymptotic Failure Probability: $\lim\limits_{n \to \infty} F_p( \cal{S})$

访问策略Access Strategy Z定义了访问每个Q的概率$P_Z(Q)$, 其中 $\sum_{Q\in\cal{S}}P_Z(Q)=1$

Z在节点$v_i$上的负载 $L_Z(v_i)=\sum_{Q\in\cal{S}, v_i\in Q}P_Z(Q)$

Z在 $\cal{S}$上的负载 $L_Z(\cal{S})=max_{v_i\in\cal{S}}L_Z(v_i)$

$\cal{S}$的负载 $L(\cal{S})=min_ZL_Z(\cal{S})$

简单地说，负载刻画了 $\cal{S}$中压力最大的节点的压力的极小值。

关于几种Quorum System可以参见重新审视Paxos协议的Quorum问题。

B-Grid Quorum System：

n=hrd，布置成hr行，d列，每组r行组成一个band，同一个band的一列的r个celll称为mini-column。Quorum是每个band的一个mini-column和某个band的每个mini-column的每个元素组成，共d+hr-1个元素。

结论1：Majority Quorum System的渐进故障概率是0。

结论2：Grid Quorum System的渐进故障概率是1。

结论3：Grid Quorum System负载最优，为$\Theta(1/\sqrt{n})$

结论4：B-Grid Quorum System拥有Majority Quorum System的渐进故障概率，和Grid Quorum System负载。Interesting…