Pith. sign in

REVIEW 3 major objections 5 minor 43 references

Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that a decentralized create-if-late rule lets random-walk learning survive a stealthy node that probabilistically eats every walk that visits it, converging with a quantifiable bias.

desk verdict The CIL mechanism and population-boundedness results are worth taking seriously, but Theorem 3's convergence claim is mathematically wrong as stated, and the algorithm's pseudocode doesn't match the analyzed rule. read the letter →

arxiv 2601.07674 v2 pith:OVOHVS6R submitted 2026-01-12 cs.MA cs.LG

Xingran Chen , Parimal Parag , Rohit Bhagat , Salim El Rouayheb This is my paper · ORCID
classification cs.MAcs.LG MSC 60J1068W1590C25
keywords randomwalkdecentralizedlearningPac-ManattackCreate-If-Lateself-creatingwalksquasi-stationarydistributionRW-SGDconvergenceadversarialtermination
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper considers decentralized learning in which model updates travel as random-walk tokens on a network, and a single malicious node—the 'Pac-Man'—silently terminates any walk that visits it, so eventually every walk dies and learning halts with no alarm raised. The paper proposes Create-If-Late (CIL): each benign node creates a new walk, copying the last walk that visited it, whenever no walk has visited for a preset number of time slots. The main claim is that CIL guarantees the walk population never becomes permanently extinct, stays almost surely bounded, and lets random-walk stochastic gradient descent converge to a biased optimum, with the bias explicitly bounded and with at most linear slowdown. If correct, this gives a fully decentralized, parameter-estimation-free defense against a stealthy termination adversary.

What carries the argument

The central object is the parent–child chain of random walks and its effective transition matrix [P_chain]_{uv} = Q^(ζ)_{uv} / Σ_v Q^(ζ)_{uv}, the row-normalized sub-stochastic matrix of the absorbed chain on benign nodes. CIL's creation rule—replicate the cached last visitor at any benign node that has gone A_u slots unvisited—supplies the infinite lineage that this chain describes; the quasi-stationary distribution ν^(ζ) (normalized leading left eigenvector of Q^(ζ)) is the stationary distribution of that chain and drives the learning bias. The boundedness results rest on a d-step drift inequality E[Z_{t+d} − Z_t | F_t] ≤ −cζ Z_t + (N−1)d, where d is the maximum time to reach the Pac-Man n

What would settle it

Run CIL on a small graph with ζ=1 and A large, track one lineage for a long time, and compare the empirical transition frequencies between benign nodes to the row-normalized Q^(1); also compare the lineage's stationary distribution to ν^(1). A statistically significant mismatch—especially on a graph where the cache location differs from the parent's death location—would refute the claimed effective-chain model.

Watch

Extended reading notes

Core claim

Under CIL, each parent–child lineage of random walks can be condensed into a single effective random walk whose transition matrix is the row-normalized sub-stochastic matrix Q^(ζ), obtained by restricting the walk to benign nodes and removing the absorbing edge to death. The limiting distribution of this effective walk is the quasi-stationary distribution ν^(ζ) of the absorbed Markov chain—the leading left eigenvector of Q^(ζ). Consequently RW-SGD converges to the minimizer of a surrogate objective that samples benign nodes according to ν^(ζ), and the distance from this biased optimum to the true optimum is bounded by (1/μ)∥∇f(x̃*)∥. In addition, the walk population is almost surely bounded

Load-bearing premise

The convergence theorem hinges on treating each parent–child lineage as one memoryless random walk with transition matrix equal to the row-normalized sub-stochastic matrix; in the real algorithm, a new walk is born at a node that has waited too long, using a cached copy from an earlier visit, which can jump backward and give the lineage memory—if that equivalence breaks, Theorem 3 no longer describes the implemented rule.

Editorial extensions

If this is right

  • Decentralized learning with random walks can tolerate a stealthy walk-terminating adversary using only local visit timestamps, with no centralized detection, no replication, and no estimation of the number of live walks.
  • The final model is provably biased: it solves a surrogate problem that samples benign nodes according to the quasi-stationary distribution ν^(ζ); as the termination probability ζ tends to 0, this distribution approaches the original sampling distribution and the bias vanishes.
  • The expected peak number of walks can be made independent of network size by choosing the creation probability q = Θ(1/N^2) on complete graphs, and remains bounded on all graphs.
  • Temporary extinctions slow learning by at most a constant factor: the expected number of completed gradient steps up to time t is at least (N/ζ)/(N/ζ + A − 1 + 1/q) · t, so convergence is linear in clock time despite interruptions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The CIL rule is a generic 'timeout-and-recreate' primitive: any token-passing distributed algorithm that can lose tokens silently—consensus, data collection, monitoring—could use local idle time to re-spawn tokens without needing to count them; the paper's drift argument suggests a design checklist for stable population control in such systems.
  • The proof treats the lineage as a memoryless chain, but the actual CIL creation jumps back in time to a cached copy at the waiting node; this is the main residual risk. A stress test would compare the empirical transition behavior along real CIL lineages with the row-normalized Q^(ζ).
  • The bias characterization could be inverted into a detection heuristic: if the final model deviates from what the known stationary distribution would produce, the network can infer that some node is absorbing walks, without labeling any node.
  • The paper's population results suggest a practical tuning strategy: set the creation probability small enough that expected walk count is O(1) in network size, making communication overhead scale gracefully, while keeping the threshold A small enough that revival delay after extinction stays bounded.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies decentralized random-walk (RW) algorithms under a 'Pac-Man' adversary that probabilistically terminates any RW visiting a malicious node. It proposes the CREATE-IF-LATE (CIL) algorithm, in which benign nodes that have not been visited for a threshold number of slots create a new RW from a cached copy of the last visiting RW. The paper claims three properties: no permanent extinction, almost sure boundedness of the RW population, and convergence of RW-SGD to a biased optimum with bounded deviation. Theorems 1 and 2 address population boundedness; Theorem 3 and Proposition 1 claim convergence and bias quantification, with the limiting sampling distribution identified as the quasi-stationary distribution (QSD) of a sub-stochastic transition matrix. The main technical problem is that Theorem 3's limiting distribution is inconsistent with the effective chain transition matrix derived in Eq. (13) and Appendix D.

Significance. The threat model is relevant and the CIL mechanism is a clean, fully decentralized idea. If the convergence theorem were correct, the paper would provide a useful resilience guarantee for RW-based decentralized learning. The population-level results (Theorems 1 and 2) appear plausible and are supported by simulations. However, the central learning guarantee is not established: the paper equates two different mathematical objects — the QSD of the absorbed chain and the stationary distribution of a row-normalized conditional chain — and the effective-chain construction does not correspond to the actual CIL process. Since Theorem 3 is the paper's main theoretical contribution, this is a load-bearing correctness failure rather than a presentation issue.

major comments (3)
  1. [§VI, Theorem 3; Eqs. (12)–(13); Appendix D] The theorem identifies the limiting sampling distribution with the QSD ν^(ζ), defined in Definition 5 as the normalized left eigenvector of Q^(ζ). But Eq. (13) and Appendix D define the effective chain transition as P_chain = D^{-1} Q^(ζ), where D is the diagonal matrix of row sums of Q^(ζ), i.e., conditioning a single RW on not being absorbed at the next step. The stationary distribution π of P_chain solves π_v = Σ_u π_u Q_uv / s_u, with s_u = Σ_v Q_uv; this equals the QSD only when all row sums s_u are equal. On non-regular graphs they are not. For example, for ζ=1 on the diamond graph with Pac-Man at node 1 and edges 1-2, 2-3, 3-4, 2-4, the row sums of Q over benign nodes are (2/3, 1, 1); the QSD is approximately (0.363, 0.319, 0.319), while the stationary distribution of the row-normalized chain is uniform (1/3, 1/3, 1/3). Thus the limit in Eq. (12) is not the stationary distribution
  2. [§VI, Definition 6; Appendix C] The 'effective single RW' construction does not match the CIL mechanism. CIL creates a child at a benign node u after A_u slots without visits, using a cached copy of the last RW that visited u. In general, u is not the node where the parent walk was terminated; the child is born at an earlier position of the parent's trajectory. The paper condenses the waiting period and states in Appendix C that X_{j'}(t_u + A_u) = u 'degenerates to' X_{j'}(t_u) = u. This erases the state jump from the death node back to u and makes the child appear before the parent's death in the condensed timeline. Consequently, the parent-child lineage is not a time-homogeneous Markov chain with transition matrix (13), and the equality ξ_{s;t} = ξ_{0;t} in Eq. (31) is not derived from the CIL rule. The assertion in Section VI that 'at least one infinite parent-child chain must almost surely exist' is also stated wi
  3. [§VI, Proposition 1(2); Appendix E] The proof of the constant-stepsize bound is not given. Appendix E says it follows from [41, Theorem 1] with substitutions and by 'artificially condensing' time intervals, but it does not verify that the hypotheses of [41] hold for the CIL chain, nor does it derive the displayed constants. Since Proposition 1(2) is part of the claimed bias characterization of the learning algorithm, this is a missing derivation, not just an omitted routine step. The authors should either supply the full argument or state the result as conditional on the cited theorem's assumptions being checked for the CIL process.
minor comments (5)
  1. [Appendix C, Lemma 3] The proof states that the restricted transition matrix Q^(ζ) is 'reducible and aperiodic' on the transient states, while Definition 4 and the preceding sentence say it is irreducible. This appears to be a typo; the word should be 'irreducible'.
  2. [Appendix A, Corollary 2] Typo: 'Pac-Mac' should be 'Pac-Man'.
  3. [§VI, Proposition 1] Typo: 'π^(ζ)_chian' should be 'π^(ζ)_chain' in the statement of Proposition 1.
  4. [Fig. 11 caption] Typo: 'publich' should be 'public'.
  5. [§VII-A] The simulation setup says 'We set both the forking and termination probabilities to 1'; the word 'forking' should be 'creation' to match CIL terminology. Also, the empirical curves in Figs. 9–11 primarily demonstrate convergence of loss; they do not directly validate the specific QSD claim in Eq. (12), which is the part of the theory that needs the most support.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained, built on stated assumptions and external QSD/convergence results.

full rationale

Walking the paper's derivation chain, I found no load-bearing step that reduces to its own inputs. The population results (Theorem 1 and Theorem 2) are proven from explicit drift bounds and recursions over the transition probabilities; the parameters c, d, and the bound O(qN^2/zeta) are derived quantities, not fitted or defined by the conclusions. Theorem 3 derives the effective sampling distribution pi_chain as the quasi-stationary distribution of the sub-stochastic matrix Q^(zeta), using standard external QSD results (Darroch-Seneta; Yaglom limits). The surrogate objective min_x E_{u~pi_chain}[f_u(x)] is defined by the model trajectory, not constructed circularly from the claimed limit. The self-citations ([15], [22], [36], [41]) appear as baselines, prior related algorithms, and a source of a convergence inequality; in all cases they are used as ordinary external mathematical/empirical support and are not the sole justification of a central result. The skeptical concern about Theorem 3--namely that the stationary distribution of a row-normalized sub-stochastic chain need not equal the QSD on non-regular graphs--is a potential correctness gap in the proof, not a circularity: it does not show that the result is equivalent to its inputs by construction. Under the stated rules, correctness concerns are outside the circularity score. Hence score 0.

Assumptions & free parameters 3 free parameters · 8 assumptions · 1 invented entities

The mechanism's two user-chosen parameters A and q control regeneration; the theory deliberately allows any A>=1, q<=1. The central convergence proof additionally imports four unproven structural assumptions: robust connectivity, strong-convexity/smoothness, the existence of an infinite parent-child chain, and the equivalence of that chain to the row-normalized sub-stochastic transition matrix. The last two are asserted rather than derived and are the fragile load-bearing premises.

free parameters (3)
  • creation threshold A_u = user-chosen; experiments use A=10 or 350
    Algorithm parameter controlling how long a node waits before creating a new RW; the theory allows any A>=1, but practical choice trades communication cost against delay.
  • creation probability q = user-chosen; experiments use q=1; Theorem 2 considers q=N^{-alpha}
    Controls regeneration frequency; for population control the paper suggests scaling q as N^{-alpha}; not derived from data.
  • initial walker count z0 = user-chosen; experiments use z0=1 or 10
    Initial condition; peak-population bounds depend on max(z0, q N^2 / zeta).
assumptions (8)
  • domain assumption The graph is robustly connected: benign nodes form a connected subgraph and the RW chain is aperiodic (Assumption 2).
    Ensures Q^(zeta) is irreducible enough to have Yaglom limits/QSD; excludes topologies where the Pac-Man node disconnects the benign subnetwork.
  • domain assumption Each local loss f_u is mu-strongly convex and L-smooth (Assumption 3).
    Standard RW-SGD convergence assumption; the MNIST cross-entropy experiments with Adam do not strictly satisfy it, so the empirical validation is not covered by the stated theorem.
  • domain assumption Bounded norm of the local gradient at the global optimum (Assumption 4).
    Used in Proposition 1's bias bound.
  • domain assumption Each RW evolves i.i.d. conditioned on its initial location (Assumption 1).
    The population drift analysis and chain coupling rely on independent walker movement, though CIL's shared cached-copy creation introduces statistical dependence.
  • ad hoc to paper At least one infinite parent-child chain exists almost surely.
    Stated without proof after Definition 6; not implied by non-extinction when the genealogy can branch infinitely.
  • ad hoc to paper The effective chain transition matrix equals Q^(zeta) normalized by row sums (Eq. 13).
    Derived by conditioning on non-absorption, but CIL creates children at previously visited cached nodes, so the actual lineage has memory and backward jumps; equivalence is unproven.
  • ad hoc to paper Waiting periods between parent death and child creation can be condensed without changing convergence.
    Used in Theorem 3 and Proposition 2; ignores staleness of the cached model and discards parent updates not on the chosen lineage.
  • standard math Finite absorbing Markov chains have unique QSD/Yaglom limits.
    Imported from Darroch-Seneta and Yaglom-limit literature; however, the proof text simultaneously calls Q^(zeta) irreducible and reducible, so the applicability is presented inconsistently.
invented entities (1)
  • Virtual death node 0
    purpose: Absorbing state in the augmented graph P' to represent termination by Pac-Man (Definition 3).
    A mathematical bookkeeping device, not a physical claim; it has no falsifiable consequences outside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks." pith.science (2026). https://pith.science/paper/OVOHVS6R

@misc{pith2026260107674,
  author       = {Pith},
  title        = {Pith review of: Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OVOHVS6R}},
  note         = {Machine review of arXiv:2601.07674}
}
read the original abstract

Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the CREATE-IF-LATE (CIL) algorithm, which is a fully decentralized, resilient mechanism that enables self-creating RWs and prevents RW extinction in the presence of Pac-Man. Our theoretical analysis shows that the CIL algorithm guarantees several desirable properties, such as (i) non-extinction of the RW population, (ii) almost sure boundedness of the RW population, and (iii) convergence of RW-based stochastic gradient descent even in the presence of Pac-Man with a quantifiable deviation from the true optimum. Moreover, the learning process experiences at most a linear time delay due to Pac-Man interruptions and RW regeneration. Our extensive empirical results on both synthetic and public benchmark datasets validate our theoretical findings.

Figures

Figures reproduced from arXiv: 2601.07674 by the authors.

Figure 1
Figure 1. An illustration of the Pac-Man attack: A malicious [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. (a): Comparison of the number of RWs under the CIL [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. An example of a chain of RWs. When a benign node [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Loss v.s. learning steps on a complete graph: compar [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 6
Figure 6. Figure 6: Number of RWs over time on different graphs when [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 5
Figure 5. Figure 5: Number of RWs over time on different graphs. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 7
Figure 7. Figure 7: Expected number of RWs over time on different [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: Comparison of the number of RWs under the CIL and [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 9
Figure 9. Figure 9: Loss function v.s. learning steps on different graphs. [PITH_FULL_IMAGE:figures/full_fig_p011_9.png]
Figure 10
Figure 10. Figure 10: Loss function v.s. learning steps on different graphs [PITH_FULL_IMAGE:figures/full_fig_p012_10.png]
Figure 11
Figure 11. Figure 11: Loss function v.s. learning steps on different graphs [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 3 linked inside Pith

  1. [41]

    The entrapment problem in random walk decentralized learning,

    Z. Liu, S. Rouayheb, and M. Dwyer, “The entrapment problem in random walk decentralized learning,” inIEEE ISIT, 2024. 14 APPENDIXA PROOF OFTHEOREM1 Definition 7.LetPr u denote the probability measure under which the RWjstarts at nodeu, i.e.,X j(0) =u. Given a distributionνover the node setV, we define the mixed law Prν ≜ Z u∈V Prudν(u), which corresponds ...

    2024

  2. [1]

    Random walks on graphs,

    L. Lovász, “Random walks on graphs,”Combinatorics, Paul Erd˝ os is eighty, vol. 2, pp. 1–46, 1993

    1993

  3. [2]

    D. A. Levin and Y . Peres,Markov Chains and Mixing Times, 2nd ed. American Mathematical Society, 2017

    2017

  4. [3]

    Distributed asynchronous optimal routing in data networks,

    J. Tsitsiklis and D. Bertsekas, “Distributed asynchronous optimal routing in data networks,”IEEE Transactions on Automatic Control, vol. 31, no. 4, pp. 325–332, 2003

    2003

  5. [4]

    A unified theory of decentralized SGD with changing topology and local updates,

    A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized SGD with changing topology and local updates,” inProceedings of the 37th International Conference on Machine Learn- ing, vol. 119, 2020, pp. 5381–5393

    2020

  6. [5]

    The pagerank citation ranking: Bringing order to the web,

    L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web,” Stanford InfoLab, Technical Report, 1999

    1999

  7. [6]

    Random-walk com- putation of similarities between nodes of a graph with application to collaborative recommendation,

    F. Fouss, A. Pirotte, J. Renders, and M. Saerens, “Random-walk com- putation of similarities between nodes of a graph with application to collaborative recommendation,”IEEE Transactions on knowledge and data engineering, vol. 19, no. 3, pp. 355–368, 2007

    2007

  8. [7]

    Smartwalk: Enhancing social network security via adaptive random walks,

    Y . Liu, S. Ji, and P. Mittal, “Smartwalk: Enhancing social network security via adaptive random walks,” inProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016, pp. 492–503

    2016

Show all 43 references
  1. [8]

    Supervised random walks: predicting and recommending links in social networks,

    L. Backstrom and J. Leskovec, “Supervised random walks: predicting and recommending links in social networks,” inProceedings of the fourth ACM international conference on Web search and data mining, 2011, pp. 635–644

    2011

  2. [9]

    Heteroge- neous graph neural network,

    C. Zhang, D. Song, C. Huang, A. Swami, and N. Chawla, “Heteroge- neous graph neural network,” inProceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, 2019, pp. 793–803

    2019

  3. [10]

    A simple peer-to-peer algorithm for distributed optimization in sensor networks,

    B. Johansson, M. Rabi, and M. Johansson, “A simple peer-to-peer algorithm for distributed optimization in sensor networks,” in46th IEEE Conference on Decision and Control, 2007, pp. 4705–4710

    2007

  4. [11]

    Walk for learning: A random walk approach for federated learning from heterogeneous data,

    G. Ayache, V . Dassari, and S. E. Rouayheb, “Walk for learning: A random walk approach for federated learning from heterogeneous data,” IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 929–940, 2023

    2023

  5. [12]

    Coupled-space attacks against random-walk-based anomaly detection,

    Y . Lai, M. Waniek, L. Li, J. Wu, Y . Zhu, T. P. Michalak, T. Rahwan, and K. Zhou, “Coupled-space attacks against random-walk-based anomaly detection,”IEEE Transactions on Information Forensics and Security, vol. 19, pp. 9315–9329, 2024

    2024

  6. [13]

    Enhancing sybil detection via social-activity networks: A random walk approach,

    X. Zhang, H. Xie, P. Yi, and J. Lui, “Enhancing sybil detection via social-activity networks: A random walk approach,”IEEE Transactions on Dependable and Secure Computing, vol. 20, no. 2, pp. 1213–1227, 2023

    2023

  7. [14]

    Robustness of random walk on a graph against adversary attacks,

    H. Kawamura, S. Shiina, H. N. Aung, and H. Ohsaki, “Robustness of random walk on a graph against adversary attacks,” in2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMP- SAC), 2024, pp. 1080–1088

    2024

  8. [15]

    Self-duplicating random walks for resilient decentralized learning on graphs,

    M. Egger, G. Ayache, R. Bitar, A. Wachter-Zeh, and S. E. Rouayheb, “Self-duplicating random walks for resilient decentralized learning on graphs,” inGLOBECOM 2024 - 2024 IEEE Global Communications Conference, 2024, pp. 2960–2965

    2024

  9. [16]

    Implementing fault-tolerant services using the state ma- chine approach: A tutorial,

    F. B. Schneider, “Implementing fault-tolerant services using the state ma- chine approach: A tutorial,”ACM Computing Surveys (CSUR), vol. 22, no. 4, pp. 299–319, 1990

    1990

  10. [17]

    The part-time parliament,

    L. Lamport, “The part-time parliament,”ACM Transactions on Computer Systems (TOCS), vol. 16, no. 2, pp. 133–169, 1998

    1998

  11. [18]

    The byzantine generals prob- lem,

    L. Lamport, R. Shostak, and M. Pease, “The byzantine generals prob- lem,”ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 4, no. 3, pp. 382–401, 1982

    1982

  12. [19]

    A survey of rollback-recovery protocols in message-passing systems,

    E. N. Elnozahy, L. Alvisi, Y . Wang, and D. B. Johnson, “A survey of rollback-recovery protocols in message-passing systems,”ACM Comput- ing Surveys (CSUR), vol. 34, no. 3, pp. 375–408, 2002

    2002

  13. [20]

    Unreliable failure detectors for reliable distributed systems,

    T. D. Chandra and S. Toueg, “Unreliable failure detectors for reliable distributed systems,”Journal of the ACM (JACM), vol. 43, no. 2, pp. 225–267, 1996

    1996

  14. [21]

    Walrand and P

    J. Walrand and P. Varaiya,High-performance communication networks (2nd ed.). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1999

    1999

  15. [22]

    Self-regulating random walks for resilient decentralized learning on graphs,

    M. Egger, R. Bitar, G. Ayache, A. Wachter-Zeh, and S. E. Rouayheb, “Self-regulating random walks for resilient decentralized learning on graphs,”arXiv preprint arXiv:2407.11762, 2024, revised February 10, 2025

    2024 arXiv

  16. [23]

    T. E. Harris,The Theory of Branching Processes. RAND Corporation, 1964

    1964

  17. [24]

    On markov chain gradient descent,

    T. Sun, Y . Sun, and W. Yin, “On markov chain gradient descent,” Advances in neural information processing systems, vol. 31, 2018

    2018

  18. [25]

    Walkman: A communication-efficient random-walk algorithm for decentralized optimization,

    X. Mao, K. Yuan, Y . Hu, Y . Gu, A. H. Sayed, and W. Yin, “Walkman: A communication-efficient random-walk algorithm for decentralized optimization,”IEEE Transactions on Signal Processing, vol. 68, pp. 2513–2528, 2020

    2020

  19. [26]

    Coulouris, J

    G. Coulouris, J. Dollimore, T. Kindberg, and G. Blair,Distributed Systems: Concepts and Design. Addison-Wesley Publishing Company, May 2011

    2011

  20. [27]

    Stochastic gradient descent under markovian sampling schemes,

    M. Even, “Stochastic gradient descent under markovian sampling schemes,” inProceedings of the 40th International Conference on Machine Learning, 2023

    2023

  21. [28]

    A randomized incremental subgradient method for distributed optimization in networked systems,

    B. Johansson, M. Rabi, and M. Johansson, “A randomized incremental subgradient method for distributed optimization in networked systems,” SIAM Journal on Optimization, vol. 20, no. 3, pp. 1157–1170, 2010

    2010

  22. [29]

    On markov chain gradient descent,

    T. Sun, Y . Sun, and W. Yin, “On markov chain gradient descent,” in Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp. 9918–9927

    2018

  23. [30]

    Distributed asynchronous optimal routing in data networks,

    “Distributed asynchronous optimal routing in data networks,”IEEE Transactions on Automatic Control, vol. 31, no. 4, pp. 325–332, 1986

    1986

  24. [31]

    Collet, S

    P. Collet, S. Martínez, and J. S. Martín,Quasi-Stationary Distributions: Markov Chains, Diffusions and Dynamical Systems, ser. Probability and Its Applications. Springer, 2012

    2012

  25. [32]

    On quasi-stationary distributions in absorbing discrete-time finite markov chains,

    J. N. Darroch and E. Seneta, “On quasi-stationary distributions in absorbing discrete-time finite markov chains,”Journal of Applied Prob- ability, vol. 2, no. 1, pp. 88–100, 1965

    1965

  26. [33]

    Expander graphs and their applications,

    S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications,”Bulletin of the American Mathematical Society, vol. 43, no. 4, pp. 439–561, 2006

    2006

  27. [34]

    The mnist database of handwritten digit images for machine learning research,

    L. Deng, “The mnist database of handwritten digit images for machine learning research,”IEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141 – 142, 2012

    2012

  28. [35]

    Measuring the effects of non- identical data distribution for federated visual classification,

    T. H. Hsu, H. Qi, and M. Brown, “Measuring the effects of non- identical data distribution for federated visual classification,” 2019, arXiv:1909.06335

    2019 arXiv

  29. [36]

    Random walk learning and the pac-man attack,

    X. Chen, P. Parag, R. Bhagat, Z. Liu, and S. E. Rouayheb, “Random walk learning and the pac-man attack,” 2025, arXiv:2508.05663

    2025 arXiv

  30. [37]

    Durrett,Probability: Theory and Examples

    R. Durrett,Probability: Theory and Examples. Thomson, Brooks Cole, 2019

    2019

  31. [38]

    Yaglom limits can depend on the starting state,

    R. D. Foley and D. R. McDonald, “Yaglom limits can depend on the starting state,”Journal of Applied Probability, vol. 54, no. 3, pp. 726– 734, 2017

    2017

  32. [39]

    Billingsley,Probability and Measure, 3rd ed., ser

    P. Billingsley,Probability and Measure, 3rd ed., ser. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons Inc., 1995

    1995

  33. [40]

    Boyd and L

    S. Boyd and L. Vandenberghe,Convex Optimization. Cambridge University Press, 2004

    2004

  34. [42]

    Whenζ= 1, the absorbing stateA={1, w}, so ˜πt = [0, πchain,t], whereπ chain;t is a discrete distribution supported on a finite set of sizeN, and lim t→∞ ˜πt = [0, ν(1)]

  35. [43]

    When0< ζ <1, the absorbing stateA={w}, so˜π t = πchain,t, whereπ chain;t is a discrete distribution supported on a finite set of sizeN+ 1, and lim t→∞ ˜πt =ν (ζ). APPENDIXD PROOF OF(13) In fact, as discussed before, we condense the time interval between the termination of the ...

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.