Fast Distributed MIS and Maximal Matching on Spatial and PLB-Bounded Scale-Free Networks: A Single-Event Meta-Theorem with Geometry and PLB-U/L/N

We prove an axiomatic meta-theorem yielding O(log log n)-round randomized algorithms for maximal independent set (MIS) and maximal matching on broad classes of scale-free networks. Our framework unifies two flavors: (i) geometry-driven rank-1 models (e.g., GIRG/soft-HRG) via a single high-probability uniformity event E that regularizes occupancies, cross-edges, and hub counts across all shells without mentioning degree-or priority-defined sets; and (ii) powerlaw bounded (PLB) degree families formalized by PLB-U (upper tail), PLB-L (lower tail), and PLB-N (size-biased neighbor tail). Our main results require PLB-N (or rank-1 models that imply PLB-N); PLB-U/L alone does not suffice. Our algorithms process vertices in degree bands. Hub-hub sparsity (from PLB-U via a weight pivot) gives bounded degeneracy inside each band; R = O(1) independent micro-iterations of randomized greedy per phase stabilize progress (via concentration). We expose a κ-fraction of edges per vertex using a per-edge public hash, and use PLB-N to sum the (decaying) band-mass effects across bands. With γ := τ − 2 ∈ (0, 1) and any constant κ ∈ (0, 1/4), the per-phase survival probability for degree ≈ 2 J is exp(−Θ(2 J(γ−κ(1−γ)))). Setting κ eff := (γ − κ(1 − γ))/2 > 0 yields a double-exponential degree cascade ∆ i+1 ≤ ∆ 1−κ eff i w.h.p.. After O((1/κ eff) log log n) phases, the maximum degree drops to polylog(n); any standard finisher with round complexity O(log ∆) + (log log n) then completes in O(log log n) rounds. Under geometry, the residual is solved in another O(log log n) rounds (and O(1) on typical threshold-HRG instances). In Congest, messages are O(log n) bits per edge per round.