Constant-Round Gossip Consensus: Push-Sum on Non-Reversible Lifted Markov Chains for Decentralized Optimization

Gossip consensus on real-world networks is bottlenecked by the spectral gap: state-of-the-art methods require Ω(√n) communication rounds on graphs with community structure. This barrier persists because all existing gossip protocols require doubly stochastic weight matrices, which preclude the non-reversible Markov chain dynamics known to quadratically accelerate mixing. Push-sum consensus (2003) and non-reversible lifted chains (1999) have each been known for over two decades, but belong to disjoint research communities and have never been combined. We combine them: PS-Lifted achieves O(1) gossip convergence—14 rounds at n = 100,000 vs. 2,217 for FDLA (158×)—and we prove this is necessary, as the lifted spectral gap is statistically constant (0.245·n⁻⁰·⁰⁰⁶, bootstrap 95% CI for exponent includes zero). A closed-form parameter rule (pc from λ₂, MAE = 0.06) eliminates grid search, a topology-adaptive router achieves 23/23 correct method selection, and logarithmic 8-bit quantization matches 64-bit convergence where linear 8-bit diverges—yielding 44–923× energy savings. Under asynchronous operation at 10% node participation, Local SGD with PS-Lifted surpasses synchronous training accuracy (91.1% vs 85.6%) through implicit noise regularization, and triple-redundant encoding eliminates Byzantine vulnerability (error 0.000 at 20% adversaries). As a distributed Kalman filter primitive, a single PS-Lifted gossip step outperforms 20 FDLA steps (RMSE 0.180 vs 0.198); with 8-bit quantization, PS-Lifted achieves better tracking accuracy than full-precision FDLA at 3.6× less bandwidth. PS-Lifted is the first gossip algorithm whose convergence time does not grow with network size, making constant-time distributed consensus, optimization, and inference practical on the bottleneck topologies that dominate real deployments.