5
$\begingroup$

In the Paxos consensus protocol, a fact that follows from its construction is "any two majority sets of acceptors will have at least one acceptor in common". This observation can be extended to any N majority sets of acceptors having either at least one acceptor in common, or acceptors that are distinctly present in each N-1 sets of acceptors.

"Therefore if two proposals are agreed to by a majority, there must be at least one acceptor that agreed to both. This means that when another proposal, for example, is made, a third majority is guaranteed to include either the acceptor that saw both previous proposals or two acceptors that saw one each."

I have an intuitive understanding of why this is so (should be a simple pigeonhole principle application), but I am having difficulty proving this formally. I would like a formal proof.

$\endgroup$
3
$\begingroup$

Let $A,B,C$ be the first, second and third majorities. If there are $M$ players, we can think of $A,B,C$ as subsets of $[M] = \{1,\ldots,M\}$ satisfying $|A|,|B|,|C|>M/2$.

If $A,B$ were disjoint then $|A \cup B| = |A| + |B| > M$, which contradicts $A \cup B \subseteq [M]$; that's why two majorities always have an acceptor in common.

If $C$ intersects $A \cap B$ then the third majority includes an acceptor that saw both previous proposals, so suppose that $C$ is disjoint from $A \cap B$. Define $$ A' = A \setminus (A \cap B), \;\;\; B' = B \setminus (A \cap B) \;\;\; U = [M] \setminus (A \cap B). $$ In order to show that the third majority includes two acceptors that saw one of the previous proposals each, we need to show that $C$ intersects both $A'$ and $B'$. If $C$ didn't intersect $A'$ then $|C \cup A'| = |C| + |A'| > M - |A\cap B|$, which contradicts $C \cup A' \subseteq U$ since $|U| = M - |A\cap B|$; so $C$ must intersect $A'$. Similarly, $C$ must intersect $B'$.

$\endgroup$
  • $\begingroup$ Now I'm convinced. Thanks. My understanding hiccuped for a moment where you used $|C \cup A'| = |C| + |A'| > M - |A\cap B|$ rather than explicitly stating that $|C| + |A'| > M$, which still contradicts $C \cup A' \subseteq U$. (I guess I was wondering the point of the pedantry). Anyways, how does one go about extending this proof for the N majorities case? A sketch or hint would suffice. $\endgroup$ – Grayskin Nov 2 '14 at 23:11
  • $\begingroup$ Actually we don't know that $|C|+|A'| > M$, since we removed $|A\cap B|$ elements from $A$. We only know that $|C|>M/2$ and $|A'| = |A|-|A\cap B| > M/2-|A\cap B|$, and so $|C|+|A'| > M-|A\cap B|$. Unfortunately I don't know what the general case is, so I can't help you with that, but I'm sure it's very similar. $\endgroup$ – Yuval Filmus Nov 3 '14 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.