Heaven & Hell: One-Step Hub Consensus

Nnamdi Aghanya · 2025

Read Heaven & Hell: One-Step Hub Consensus by Nnamdi Aghanya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19630.txt.

Introduction

A hub node that broadcasts to a network can steer every other node, if its voice is loud enough. Nnamdi Daniel Aghanya studies that steering in a toy model where each node holds one of two states. He gives a sharp local test for success: at each node, the weight arriving from the hub must at least match all other incoming weight combined. When the test holds, the whole network flips to the hub's state in one step.

For uniform broadcasts, the exact loudness needed equals the largest non-hub weight anywhere, and no less will do. The result survives biased update rules and one-at-a-time update orders. All theorems come with machine-checked proofs in the Coq proof assistant. The model speaks to systems where a central authority must hold a shared setting against peer pressure.

Catalog record

CREATORNnamdi Aghanya
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-19630

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Heaven & Hell: One-Step Hub Consensus Thanks: GUDraBIT Research Technical Report TR-2025-01. Nnamdi Aghanya Abstract In networked systems, enforcing a global configuration from a central authority against local peer influence is a foundational challenge. We investigate a model of influence dynamics on a finite weighted digraph where a distinguished hub node seeks to impose a desirable state, Glory , upon the entire network. Our central objective is to identify a sharp, local, and efficiently verifiable graph-theoretic condition that guarantees global convergence to Glory in a single synchronous update, irrespective of the initial network state. Our primary contribution is an exact necessary-and-sufficient condition based on the relative weights of incoming edges from the hub versus all other nodes. We specialise this to derive a sharp threshold for systems with a uniform-hub broadcast weight. The analysis is extended to a biased update rule and to asynchronous (Gauss–Seidel) updates, where we show one pass suffices under the same domination hypothesis. Every theoretical result is formally verified in the Coq proof assistant. 1 Introduction In networked systems, achieving global consensus or enforcing a desired configuration is a foundational challenge, particularly when nodes are subject to conflicting local influences. We consider a scenario where a designated control node, or hub , attempts to steer the entire system towards a specific state (termed Glory ) against the potentially opposing influence of other nodes, which may promote an alternative state, Gnash . This model’s diverse phenomena range from a trusted server disseminating correct software versions in a peer-to-peer network to a central bank managing inflation expectations among regional actors. Our central objective is to identify a sharp, local, and efficiently verifiable graph-theoretic condition that guarantees global convergence to Glory in a single synchronous update, irrespective of the initial network state. Such a one-step guarantee is crucial for applications demanding rapid and reliable configuration control. Classical binary-state dynamics include voter/majority models [ 1 , 2 ] , linear-threshold processes [ 3 ] , and Glauber-type updates on Ising graphs [ 4 ] . Those lines typically study asymptotic behaviour, spectral or energy-based criteria, or average-case initialisations. Control-theoretic work on distributed consensus (and Byzantine-robust variants) focuses on linear averaging or fault bounds [ 5 , 6 ] , again with multi-step convergence. Our setting differs in three respects: a non-linear, score-based update; an adversarial (worst-case) initial state; and an exact one-step criterion. The condition is vertex-local (hub-vs-rest inequality on in-weights), needs no spectral computation, and applies to arbitrary non-negative weights. This perspective is also tied to influence and seeding problems [ 3 ] . Linear-threshold cascades and influence maximisation address reachability over time under budgeted interventions; here, the budget is concentrated at a single hub, whether one step suffices for universal adoption. The failure mode without a hub is immediate (two cycles under parity on a 4-cycle; see Figure 2 ); the hub breaks such cycles once its inbound weight into each non-hub exceeds the competing inbound from the rest. The empirical sweep in Figure 1 matches the predicted threshold \mathrm{max\_rest} . Our contributions are as follows: (i) We establish an exact necessary-and-sufficient condition for one-step convergence, expressed as a simple inequality between hub and non-hub influence at each vertex ( Theorem 2.1 ). (ii) This general result is specialised to the practical case of a uniform-hub broadcast, yielding a sharp threshold characterised by a single global graph parameter, \mathrm{max\_rest} ( Theorem 2.2 ). (iii) We extend our analysis to include a biased ( \tau ) update rule, providing a correspondingly adjusted convergence condition ( Theorem 2.4 ). (iv) We demonstrate that the same hub domination hypothesis guarantees convergence in one pass under asynchronous (Gauss–Seidel) updates ( Theorem A.3 ). (v) Finally, every theoretical result presented is backed by a formal Coq development, aligning each theorem with a mechanised proof and ensuring its correctness. 1 1 1 Coq Files can be found here . 2 Methodology Model and Update Rules. We consider a finite vertex set \mathcal{V} with a distinguished hub g\in\mathcal{V} . The network is a weighted directed graph where edge weights are given by a function w:\mathcal{V}\times\mathcal{V}\to\mathbb{N} . Each vertex v\in\mathcal{V} can be in one of two states from the set \{\textsc{Glory},\textsc{Gnash}\} . The system’s configuration is a state function s:\mathcal{V}\to\{\textsc{Glory},\textsc{Gnash}\} . For any vertex v , its incoming influence from peers in a state x is quantified by a score function, \mathrm{score}_{x}(s,v)\coloneqq\sum_{u\in\mathcal{V}}w(u,v)\cdot\mathbb{I}(s(u)=x) , where \mathbb{I}(\cdot) is the indicator function. The update rule prioritises the hub’s state. We define a hub-forced state s_{g} , where s_{g}(v)=\textsc{Glory} if v=g and s_{g}(v)=s(v) otherwise. A vertex v updates its state based on a majority vote of incoming influence in this hub-forced state. The unbiased update rule, \mathrm{next}_{\mathrm{heaven}} , is defined as: \mathrm{next}_{\mathrm{heaven}}(s,v)\coloneqq\begin{cases}\textsc{Glory}&\text{if }v=g\\ \textsc{Glory}&\text{if }v\neq g\text{ and }\mathrm{score}_{\textsc{Glory}}(s_{g},v)\geq\mathrm{score}_{\textsc{Gnash}}(s_{g},v)\\ \textsc{Gnash}&\text{if }v\neq g\text{ and }\mathrm{score}_{\textsc{Glory}}(s_{g},v)<\mathrm{score}_{\textsc{Gnash}}(s_{g},v)\end{cases} The \tau -biased variant, \mathrm{next}_{\mathrm{heaven}}^{\tau} , introduces a non-negative bias \tau(v) to the Glory score, thereby comparing \mathrm{score}_{\textsc{Glory}}(s_{g},v)+\tau(v) against \mathrm{score}_{\textsc{Gnash}}(s_{g},v) . For analysis, we partition the total incoming weight at any vertex v into that from the hub, \mathrm{hub\_weight}(v)\coloneqq w(g,v) , and that from all other nodes, \mathrm{rest\_weight}(v)\coloneqq\sum_{u\neq g}w(u,v) . The foundational identities and bounds relating these weights to the score functions are derived in Appendix A . 2.1 Main Theorems We present our primary results concerning the conditions for guaranteed one-step convergence. The proofs are based on the lemmas and score properties established in Appendix A . Theorem 2.1 (One-step Convergence, Unbiased) . Global convergence to Glory in one synchronous step, from any initial state, is guaranteed if and only if the hub’s influence dominates the collective non-hub influence at every other vertex: (\forall s,v,\ \mathrm{next}_{\mathrm{heaven}}(s,v)=\textsc{Glory})\iff(\forall v\neq g,\ \mathrm{hub\_weight}(v)\geq\mathrm{rest\_weight}(v)) Proof. The proof is deferred to the appendix, see Theorem A.2 . ∎ Theorem 2.2 (Uniform Hub Threshold) . If the hub influence is uniform, i.e., \mathrm{hub\_weight}(v)=W for all v\neq g , and we define \mathrm{max\_rest}\coloneqq\max_{v\neq g}\mathrm{rest\_weight}(v) , then one-step convergence holds if and only if W\geq\mathrm{max\_rest} . Proof. By Theorem 2.1 , the system converges if and only if (\forall v\neq g,\mathrm{hub\_weight}(v)\geq\mathrm{rest\_weight}(v)) . Substituting the uniform hub weight, this becomes (\forall v\neq g,W\geq\mathrm{rest\_weight}(v)) . By A.8 , this universal condition is equivalent to W being greater than or equal to the maximum of all such rest weights, which is precisely W\geq\mathrm{max\_rest} . ∎ Theorem 2.3 (Sharpness of the Threshold) . If the uniform hub weight W is below the threshold, W<\mathrm{max\_rest} , there exists a non-hub vertex v for which the update from the all_gnash state results in Gnash . Proof. Assume W<\mathrm{max\_rest} . By the property of the maximum function ( A.10 ), there must exist a vertex v_{0}\neq g such that \mathrm{rest\_weight}(v_{0})>W . Given the uniform hub weight, this implies \mathrm{hub\_weight}(v_{0})<\mathrm{rest\_weight}(v_{0}) . By A.9 , this is the precise condition under which \mathrm{next}_{\mathrm{heaven}}(\texttt{all\_gnash},v_{0})=\textsc{Gnash} . ∎ Theorem 2.4 (One-step Convergence, \tau -Biased) . For the biased update rule, one-step convergence holds if and only if the sum of the hub’s influence and the local bias dominates the rest-influence: (\forall s,v,\ \mathrm{next}_{\mathrm{heaven}}^{\tau}(s,v)=\textsc{Glory})\iff(\forall v\neq g,\ \mathrm{hub\_weight}(v)+\tau(v)\geq\mathrm{rest\_weight}(v)) Proof. The proof follows the same structure as that of Theorem 2.1 and is presented in the appendix as part of Theorem A.2 . ∎ 3 Algorithmic Certification and Threshold Extraction The theoretical conditions translate into efficient algorithms for certifying a

Read the complete text