Two kinds of local-to-global impossibility: chromatic and anonymous

Two kinds of local-to-global impossibility: chromatic and anonymous

Standalone note. Claim: "consistent on every local view, inconsistent globally" is a symptom with two distinct mechanisms, distinguished by whether the local observers carry isotropy. Distributed computing has one impossibility theorem for each; arithmetic sits on the anonymous side, and the Grunwald–Wang special case is a worked example of it.

1. The two mechanisms

Chromatic (Herlihy–Shavit). Processes carry distinct identities. The protocol complex is a chromatic subdivision of the input complex; the symmetric group acts freely, so there is no isotropy. A task is solvable iff a simplicial map carries the protocol complex to the output complex. Obstructions are connectivity: consensus is impossible (FLP) because the protocol complex stays connected while the output complex is disconnected; k-set agreement fails by Sperner. Communication is subdivision and preserves topology, so obstructions are classes of a nerve: Čech.

Anonymous (Angluin; Yamashita–Kameda). Processes are interchangeable under a symmetry group G acting on the system. Two processes in the same orbit have the same view and behave identically. Obstructions are fixed points: leader election is possible iff some vertex is fixed by the residual symmetry. The local observers are the subgroups of G, and they act on the data. This is the model with isotropy.

The criterion. Ask whether the local observers act on the coefficients. If not, obstructions are cycles in a labelled nerve (chromatic). If so, obstructions are fixed-point failures of a group action (anonymous).

2. Two subtypes of anonymous obstruction

Let G act on a set of candidates. Two distinct impossibilities:

• Fixed-point-free: some g ∈ G moves every candidate. This is Angluin's ring: ℤ/n rotating n identical processes. Symmetry must be broken completely.
• Elementwise-fixed, globally free: every g fixes some candidate, but no candidate is fixed by all of G. Symmetry can be broken to any cyclic subgroup and election succeeds, yet the full group blocks it.

Lemma. A G-set with elementwise fixed points and no global fixed point exists iff G is noncyclic. (⇐: take ⊔_{C cyclic} G/C. ⇒: for cyclic G = ⟨g⟩, a fixed point of g is fixed by G.)

The second subtype is the Ш type: every proper subgroup succeeds, the whole group fails. The obstruction is the gap between the subgroup lattice's "solvable" part (subgroups with a fixed point) and the top.

3. Arithmetic is anonymous: Grunwald–Wang

K = ℚ(√7), L = K(ζ₈), G = Gal(L/K) = (ℤ/2)² = ⟨σ, τ⟩ with σ: ζ ↦ ζ⁻¹, τ: ζ ↦ ζ⁵. The local observers are the decomposition groups, all cyclic for this K, and they act on the coefficient module μ₈. Computed by enumeration:

• H¹(G, μ₈) = ℤ/2, and every class restricts to zero on all three cyclic subgroups: Ш¹(G, μ₈) = H¹(G, μ₈) = ℤ/2.
• The task "choose an 8th root of 16": the roots ζ^k√2 form a G-set on which σ fixes ±√2, τ fixes the four ±(1±i), στ fixes ±√−2, and no root is fixed by G.

So 16 is an 8th power in every completion (each local Galois group has a fixed root) and not in K (no global fixed root). That is leader election failing in the elementwise-fixed subtype. The classical condition for the special case — K(ζ_{2^t})/K noncyclic with all decomposition groups cyclic — is the lemma's condition. Tate's theorem that H³(G, L^×) ≅ ℤ/(n/m), nonzero iff no decomposition group is all of G, is the same noncyclicity seen from rung 3. The bridge between arithmetic and permutation-group fixed points is already in use: Fein–Kantor–Schacher prove relative Brauer groups infinite via Jordan's theorem that every transitive group contains a derangement.

4. A phenotype with two genotypes

Fekete–O'Neil–O'Neil's read-only anomaly under snapshot isolation: three transactions, every pair serializable, the triple not. The constraints form a directed cycle T₂→T₁→T₃→T₂; the transactions are labelled; nothing acts on them. This is a cycle in a nerve — chromatic — despite sharing Grunwald–Wang's symptom. Borromean rings and triple Massey products are of the same cycle type. So "pairwise invisible, globally present" must be sorted by mechanism:

5. The subgroup-lattice hierarchy, computed

Anonymous computability is decided by views, and views coincide iff colour-refinement colours coincide. On a network with (ℤ/2)² symmetry whose three involutions each fix a pair of vertices and which has no globally fixed vertex (K_{2,2,2} with the orbit structure {x₁,x₂},{y₁,y₂},{z₁,z₂}): under full anonymity no vertex has a unique view; giving out labels that leave residual symmetry ⟨a⟩, ⟨b⟩, or ⟨ab⟩ produces a uniquely identifiable vertex in each case. On the ring C₄, residual ⟨r²⟩ still elects nobody; only trivial residual symmetry does. The lattice of subgroups with a fixed vertex is the whole proper lattice in the first case and {1} in the second. The Ш class is the difference between "all proper subgroups succeed" and "G fails."

6. Status

Sections 1, 3, 5 are computed or theorem-backed; the lemma in §2 is elementary. What is new here, as far as I know, is the sorting: the chromatic/anonymous split as the criterion for which impossibility theorem a domain has, arithmetic placed on the anonymous side with Grunwald–Wang as a fixed-point failure, and the fixed-point-free vs elementwise-fixed distinction within the anonymous model. What is not new: each theorem cited. Open: whether the Ш-type hierarchy has been stated in the anonymous-computing literature in subgroup-lattice form; whether Byzantine faults admit any placement (they are a second player, not a symmetry).