I know that this is a known theorem but I can't find its proof. The theorem is:
The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write operations) is $n$.
Can someone link me to a proof or an explanation?
This is the classical "critical-state argument", also called "bivalence argument", used by Fischer, Lynch, and Paterson to prove the impossibility of consensus in an asynchronous message-passing system where one processor may fail.
For (wait-free) binary consensus, the critical-state argument says that there must exist a state S of the system such that both decisions are still possible starting from S, but for every immediate successor S' of S the decision is determined. Thus we can partition the processors into two teams $\Pi_0$ and $\Pi_1$ such that a step of a processor from team $\Pi_0$ from S eventually results in decision 0 while a step of a processor from team $\Pi_1$ from S eventually results in the decision 1.
Now suppose that, in S, the next step of processor $p_0$ is to modify object $O_1$, and the next step of processor $p_1$ is to modify object $O_2\neq O_1$. Wlog we can assume $p_0\in\Pi_0$ and $p_1\in\Pi_1$. Since $O_2\neq O_1$, the steps of $p_0$ and $p_1$ commute and lead to the same state S'' regardless of their order. Moreover, since $p_0\in\Pi_0$, the consensus decision from S'' is 0. However, since $p_1\in\Pi_1$, the consensus decision from S'' is also 1, which is a contradiction.
The case in which some processors are about to perform a pure read operation similarly leads to a contradiction.
We conclude that in state S, all processors are about to modify the same object. Thus in any consensus algorithm there is at least one system state in which all processors are about to modify the same object.
