Fundamental Limits of Decentralized Self-Regulating Random Walks

Abstract

We study self-regulating random walks (SRRWs), a decentralized mechanism for maintaining a stable population of mobile tokens on a graph. Tokens move by random walks, may be lost at faulty or malicious trap nodes, and may be locally forked or terminated according to node visit ages. The goal is to prevent both extinction and runaway growth without a central coordinator. We develop a graph-aware, controller-agnostic theory for SRRWs on finite connected graphs with lazy reversible random-walk dynamics. The main technical tool is a set of node-dependent return-time tail bounds, which yield population-dependent envelope functions describing how often local ages are large enough to trigger control actions. These envelopes translate graph structure into drift certificates: when the population is small, the achieved fork rate must compensate trap-induced absorption; when the population is large, trap losses and deliberate terminations must dominate forks. Using these certificates, we characterize population corridors for which the full system-state process is positive recurrent. We also identify two fundamental limits: stable finite-communication operation requires sufficient graph-limited forking capacity to offset absorption, and recovery from burst deletions or insertions is limited by the graph-dependent frequency of eligible local visits. Finally, we describe a minimal hysteresis controller with two age thresholds, one for replenishment and one for suppression, and show that its recovery behavior follows from the same certified margin conditions. Worked examples and numerical experiments on heterogeneous graphs illustrate how the stationary distribution, return-time envelopes, drift margins, finite-cost balance, reaction-time limits, and operating corridors can be computed and validated in concrete SRRW systems.