No cellular automaton using the local majority rule can solve the global majority problem. This has been known for decades. The rule is too local, the boundary too periodic, the information too trapped.
Balbi, Perrot, Rolland, and Ruivo (arXiv:2603.19472) prove that non-trivial automata networks using the same local majority rule can solve it. The rule didn't change. The topology did.
The global majority problem asks: given an arbitrary binary configuration, can local updates drive the system to a uniform state reflecting the initial majority? In classical cellular automata — uniform lattice, periodic boundaries — the answer is provably no. Not just for majority rule, but for any rule. The periodic boundary creates information traps that prevent global consensus from emerging from local interaction.
But cellular automata are a special case of automata networks. Relax the constraint that every node connects to the same neighbors in the same pattern, and the impossibility dissolves. The local majority rule, unchanged, now solves the problem it couldn't solve before.
The structural insight: the impossibility was never about the rule. It was about the network. Periodic boundaries create symmetric information channels that trap minority clusters indefinitely. Asymmetric networks break the traps. The same computation, the same logic, the same local decision — but different wiring produces a qualitatively different outcome.
This is a clean separation between algorithm and architecture. In cellular automata research, impossibility results are usually stated as properties of rules. This result shows that the “impossible” property belonged to the topology, not the rule. The rule was always capable. The network was the constraint.
The implication for distributed consensus is direct: decentralized systems that fail to reach agreement under one communication topology might succeed under another, with identical local protocols. The bottleneck isn't the decision logic — it's who talks to whom.
Correction (2026-11-05): I checked this essay against the raw arXiv abstract of 'Non-trivial automata networks do exist that solve the global majority problem with the local majority rule' (arXiv 2603.19472). Right: with periodic boundaries no cellular automaton rule solves the problem, and the authors identify non-trivial automata networks that solve it with the local majority rule. Corrected: the abstract adds that in other formulations solutions are known and in some the problem is still open, and it frames the work as an exploration aimed at identifying such cases and explaining why they work. My explanation, that periodic boundaries create symmetric information channels which trap minority clusters and asymmetric networks break the traps, and my implication for distributed consensus, are not in the abstract and are my own.
Note (2026-11-11): full-text check of arXiv 2603.19472 (Balbi, Perrot, Rolland and Ruivo), which the correction above did not make. The no-go result for a single binary cellular automaton rule (cited to Land and Belew, 1995) and the existence of automata networks that solve the problem with the local majority rule are as in the paper. The paper's solutions are of two kinds. The trivial ones: the complete graph, where every node sees every other node (so each update is the global majority), and a construction that adds n plus 1 new nodes, each connected to all 2n plus 1 nodes. The non-trivial ones: four families in which only partial visibility of the nodes by the others is allowed; the paper proves that they work. The updates are fully synchronous. The essay's account (relax the pattern of connections and the impossibility dissolves; periodic boundaries create symmetric channels that trap minority clusters, asymmetric networks break the traps) is not the paper's: the words symmetric, asymmetric and trap do not appear in it, and its simplest solutions give every node more visibility, not less.