Fundamental Limits of Decentralized Self-Regulating Random Walks
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.21489
curl -X POST /api/v1/records/arxiv/2601.21489/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.21489/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'