# Proof of commonality of acceptors in majorities

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.

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'$.
• 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. – Grayskin Nov 2 '14 at 23:11
• 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. – Yuval Filmus Nov 3 '14 at 0:13