Pith. sign in

REVIEW 4 major objections 5 minor 16 references

Rumors on evolving graphs through stationary times

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A strong-stationary-time transfer theorem carries rumor-spreading completion bounds from independent to dependent dynamic graphs.

desk verdict Fresh transfer idea for rumor spreading on dependent graphs, but the non-Markovian extension is a backward-time construction mismatched to the forward-time lemma, and one advertised Push result doesn't fit the theorem's conditions. read the letter →

arxiv 2506.04386 v1 pith:CMBFLKAG submitted 2025-06-04 cs.DS cs.DMmath.PR

Vicenzo Bonasorte This is my paper
classification cs.DScs.DMmath.PR MSC 05C8060J1060K0568W20
keywords randomizedrumorspreadingstrongstationarytimesperfectsimulationedge-Markoviangraphsrenewalprocessescompletiontimecouplingfromthepast
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

This paper tries to establish a transfer principle: upper bounds on rumor-spreading completion time proved for independent random graphs remain valid for dependent stationary random graphs, provided the edge process has a sequence of strong stationary times with light-tailed gaps. The payoff, if true, is a plug-in strategy that reuses the existing i.i.d. literature to handle Markovian and renewal edge dynamics, including settings not previously treated. The workhorse is Lemma 1, which shows that when at increasing random times $t_1,t_2,\ldots$ the graphs are independent with the stationary edge distribution and the times do not stretch too far, any protocol with high-probability i.i.d. completion time $O(r(n))$ inherits the same bound on the dependent sequence. Applications include new $O(\log n)$ bounds for Pull and Push-Pull on edge-Markovian graphs with stationary edge probability $a/n$, a new $O(n^{k-1}\log n)$ bound for Push when $p=a/n^k$ and $q=1$, and a renewal-process example giving $O(n^{\lambda-1}\log n)$ for Push.

What carries the argument

The central object is a layered sequence of strong stationary times: a strong stationary time is a randomized stopping time $T$ at which the process state has the stationary distribution and is independent of $T$; layering independent copies of such times gives times $t_i$ at which the graph is exactly i.i.d. with the stationary edge marginal. The Markov section obtains these times from the maximal separation distance, bounding $s(k) \le 1 - (1 - \rho |\Delta|^k)^{\binom{n}{2}}$ so that under the paper's mixing condition the strong uniform time is stochastically at most a geometric random variable. The non-Markov section instead obtains candidate times from coupling from the past (CFTP): coalescing times at which the simulated state forgets its arbitrary past, yielding graphs that are stationary and independent. In the renewal example the coalescing time is geometric with parameter $1-(1-\alpha)^{\binom{n}{2}}$, producing the light-tail gaps used in the transfer.

What would settle it

Compute the law of the forward gaps $t_{i+1}-t_i$ in the renewal example; the paper establishes the tail bound (4) for the backward coalescing time of the coupling-from-the-past construction, and the transfer needs the same light-tail bound for an increasing forward sequence. If $P(t_{C r(n)} > D r(n))$ fails to vanish polynomially for the natural forward construction, the renewal $O(n^{\lambda-1}\log n)$ bound would not follow from the argument as written.

Watch

Extended reading notes

Core claim

The paper's central claim is Lemma 1: for a stationary but dependent sequence of random graphs, if there exist increasing random times $t_1,t_2,\ldots$ such that the graphs at those times are independent and drawn from the stationary marginal, and $P(t_{C r(n)} > D r(n))$ vanishes polynomially, then every protocol whose completion time on the i.i.d. sequence is $O(r(n))$ with high probability has completion time $O(r(n))$ on the dependent sequence. The proof couples the dependent rumor process to the independent process at the fresh-start times and bounds the probability of stopping too late by two vanishing terms: the i.i.d. failure probability and the probability that the $C r(n)$-th fresh start arrives late. Theorem 2 supplies the fresh-start times for edge-Markovian graphs through strong uniform times under the fast-mixing condition $|g(n)-f(n)| \le M/n^\alpha$, and Theorem 6 does the same for perfectly simulable non-Markovian processes by iterating coupling from the past. The corollaries give new bounds for Push, Pull, Push-Pull, and Flood on the Markov dynamics, and for Push on the renewal dynamics.

Load-bearing premise

The load-bearing premise is that a dependent stationary edge process has an increasing sequence of fresh-start times at which it is exactly stationary and independent of the past, with gaps light enough that the $C r(n)$-th fresh start is unlikely to arrive after $D r(n)$; in the Markov application this premise is guaranteed only under the fast-mixing condition $|g(n)-f(n)| \le M/n^\alpha$, and in the non-Markov application it is assumed rather than proved, because the coupling-from-the-past construction yields backward times.

Editorial extensions

If this is right

  • Any protocol whose i.i.d. completion time is $O(r(n))$ with high probability, for $r(n)=\Omega(\log n)$, inherits the same bound on every edge-Markovian graph satisfying the paper's mixing condition $|g(n)-f(n)|\le M/n^\alpha$.
  • The Flood protocol completes in $O(\log n / \log(1+n\pi(1)))$ and Push in $O(\log n / \min\{1,n\pi(1)\})$ with high probability on such edge-Markovian graphs.
  • For edge-Markovian graphs with stationary edge probability $\pi(1)=a/n$, the Pull and Push-Pull protocols complete in $O(\log n)$ with high probability, which the paper identifies as new in the literature.
  • In the sparse phase $p=a/n^k$, $q=1$, the Push protocol completes in $O(n^{k-1}\log n)$ with high probability; the renewal-process example yields the analogous bound $O(n^{\lambda-1}\log n)$ when the stationary edge probability is of order $1/n^\lambda$.

Reading between the lines

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

  • Editorial: The transfer is protocol-agnostic, so any future i.i.d. bound of the form $O(r(n))$ with $r(n)=\Omega(\log n)$ would automatically apply to dependent stationary graphs with light-tailed strong stationary times, extending the paper's examples to new protocols.
  • Editorial: The Markov corollaries suggest a general rule of thumb that edge dynamics mixing in $O(1)$ steps do not change the asymptotic rumor-spreading rate; a natural stress test is to compare constant-mixing Markov chains with longer-memory renewal chains of equal stationary edge probability in simulations.
  • Editorial: A reader extending the paper should check whether the iterated CFTP construction can be converted into increasing forward times $t_i$ with the stated geometric gaps; the paper writes the $t_i$ as $\tau_{i-1}-1$ from backward coalescing times, so establishing an increasing forward version would complete the renewal proof.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes a general reduction for rumor-spreading completion times on dependent edge processes. Lemma 1 states that if a stationary sequence of random graphs admits increasing random times t_i at which the graphs are independent and drawn from the stationary marginal, and the t_i have light-tailed gaps, then any protocol with O(r(n)) high-probability completion time on i.i.d. graphs also has O(r(n)) completion time on the dependent sequence. The paper applies the reduction to edge-Markovian graphs via strong uniform times, obtaining bounds for Push, Pull, Push-Pull, and Flood protocols, and then claims an extension to non-Markovian dynamics through coupling from the past, with a stationary renewal-process example.

Significance. If the Markovian part is correct, the reduction is a clean and potentially useful transfer principle: it lets known i.i.d. bounds be lifted to dependent stationary edge processes with light-tailed regeneration times. The paper explicitly credits the external i.i.d. bounds and the strong-uniform-time theory, and the Markovian applications (especially the Push bound for p = a/n^k, k>1) appear new. The non-Markovian claim is the main advertised novelty, but as written it is not established: the CFTP construction produces decreasing, backward times, while Lemma 1 requires increasing forward times. The paper is honest about relying on external results, but the central reduction and Markov application need some technical tightening before the claims can be taken as proved.

major comments (4)
  1. [Section 4.1 and Theorem 6] The proof constructs t_1 = 0, t_2 = tau_1 - 1, t_3 = tau_2 - 1, ..., where tau_1 = theta_0 <= 0 and tau_2 = theta_{tau_1 - 1} < tau_1. This is a strictly decreasing sequence lying in the past, whereas Lemma 1 requires an increasing sequence of times t_1 < t_2 < ... with t_0 = 0 and a tail bound on the forward time t_{C r(n)}. Theorem 6 instead uses P(-t_{C r(n)} > D r(n)), a bound on the distance into the past. No argument is given that forward strong stationary times with the same gap distribution exist, and the renewal process is not shown to be time-reversible. Therefore Theorem 6 and Corollary 7 do not follow from Lemma 1 as written. This is load-bearing for the 'beyond Markov' contribution.
  2. [Section 3, Eq. (1)] The step 'For suitable constants, we will bound: s(k) <= n^2 (M/n^alpha)^k <= (1/n^t)^{k-l}' leaves the constants t and l unspecified. They must be chosen independently of n for the subsequent stochastic domination T^a - l <=_st G with G ~ Geo(1 - 1/n^t) and for the tail bound to vanish polynomially. As written, it is not demonstrated that a single choice of t and l works for all sufficiently large n, since the factor M^k interacts with n through log_n M. The author should state an explicit choice (for example, t < alpha and l large enough) and prove the inequality uniformly in n.
  3. [Lemma 1] The proof uses P(N > D r(n)) <= P(t_{\bar N} > D r(n)), which implicitly requires the protocol to be monotone: the extra rounds between t_i and t_{i+1} cannot delay completion, and the rounds at the t_i are a subsequence of the original process. The lemma states a result for 'an information spreading protocol' without this assumption. Since all protocols considered in the paper are monotone, the fix is straightforward, but the lemma as stated is not valid for arbitrary protocols and the monotonicity assumption should be made explicit.
  4. [Section 4.1] The constructed times are not strong stationary times in the usual forward sense: they are not stopping times with respect to the forward filtration, and Lemma 1(1) requires the entire sequence of graphs at the selected times to be independent, not merely each X_{t_i} to be marginally stationary. The paper asserts 'i.i.d. random times such that X_{t_i} follows the stationary distribution', but the joint independence needed for Lemma 1 is not proved. This is part of the same forward/backward gap and must be repaired before the non-Markovian application is valid.
minor comments (5)
  1. [Section 2] The expression 'C n 2' should be the binomial coefficient \binom{n}{2}; please fix the notation.
  2. [Section 4.1] The term 'strong stationary times' is used for times that are not stopping times in the forward filtration; the paper should either define the generalized notion or use a different term to avoid confusion with the standard definition cited in Section 3.
  3. [Corollary 7] The condition on g(n) is ambiguous: if g(n) has a constant limit gamma >= 0, then alpha_n = g(n)/n^lambda ~ gamma/n^lambda, which is not necessarily in (0,1) for all n. State a concrete tail condition, such as g(n) bounded above by a constant less than 1 for all large n, so that alpha in (0,1).
  4. [Section 4.2, Eq. (4)] Since the t_i are decreasing, |t_i - t_{i-1}| is a coalescing-time gap; the paper should state explicitly that these gaps are independent and geometrically distributed (or supply the reference for the repeated CFTP construction) before using the sum in Corollary 7.
  5. [References] The reference to 'Daknama (2017)' cites arXiv:1801.00316, which is dated 2018; please update the year or the citation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Markov and renewal bounds are genuine reductions to external i.i.d. results via strong stationary times and CFTP; the flagged gap is a correctness issue, not a circular step.

full rationale

No circular step is present; the derivation chain is genuinely reductive rather than definitional. Lemma 1 reduces a bound on the completion time N on the dependent sequence to a union bound, P(N > D r(n)) <= P(Nbar > C r(n)) + P(t_{C r(n)} > D r(n)), where Nbar is the completion time on the i.i.d. subsequence (whose O(r(n)) bound is an external literature result, e.g., Clementi et al. 2016, Doerr & Kostrygin 2017) and the second term is a tail bound on the extracted stationary times. Neither term is the conclusion in disguise: the times t_i are constructed from the Aldous-Diaconis strong uniform time theory in the Markov section, with explicit separation-distance bounds (Equation (1)) computed from the transition matrix under the stated near-idempotence condition |g(n)-f(n)| <= M/n^alpha, and from CFTP coalescence in the non-Markov section. No parameter is fitted to data and then renamed a prediction: the sufficient conditions (r(n) = Omega(log n), alpha = g(n)/n^lambda, etc.) are stated before the conclusions, and the derived rates (e.g., n^{lambda-1} log n for Push on edge-renewal graphs) follow by algebra from external i.i.d. rates, not from the conclusions themselves. The citation to Gallo (2011) for CFTP coalescence of renewal processes is not author-overlapping in the strict sense (Gallo is the acknowledged supervisor, not a co-author of this paper), and the cited fact is independently checkable: under condition (3), coalescence per backward step has probability at least 1-alpha per edge, so the coalescing time is geometric with parameter 1-(1-alpha)^{C(n,2)}. Thus the citation is real evidence, not load-bearing self-citation. The reviewer-flagged issue that Section 4.1's CFTP construction yields decreasing past times t_1 = 0 > t_2 = tau_1 - 1 > t_3 = tau_2 - 1 > ... while Lemma 1 requires an increasing forward sequence is a correctness gap in the non-Markovian extension as written (it would need a reversal-and-shift argument), not a circularity: even if repaired, the claimed bound would still be a reduction to external i.i.d. results plus a coalescence tail, not an input to itself. Since the paper's central claims are self-contained against external benchmarks (Aldous-Diaconis separation distance bounds, Propp-Wilson CFTP, published i.i.d. rumor-spreading rates), the honest finding per the rubric is no significant circularity.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities and fits no data. The free parameters are existence constants (C, D, t, l) asserted but never quantified. The axioms are the external tools the reduction depends on: monotone protocols, Aldous-Diaconis strong uniform times, known i.i.d. bounds, and Gallo's CFTP for renewal processes.

free parameters (2)
  • separation constants t and l = unspecified
    Eq (1) asserts s(k) <= (1/n^t)^(k-l) 'for suitable constants'; the validity depends on alpha, M, and h(n), which can grow as n^k, but the constants are never specified or checked.
  • Lemma 1 constants C and D = unspecified
    Lemma 1 requires existence of positive constants C,D such that P(t_{C r(n)} > D r(n)) vanishes polynomially; they are assumed large enough, not derived.
assumptions (4)
  • domain assumption The rumor-spreading protocols (Push, Pull, Push-Pull, Flood) are monotone in the edge set: adding edges cannot increase completion time.
    Used implicitly in Lemma 1 to compare the dependent process at stationary times with the i.i.d. process; not stated in the paper.
  • standard math Aldous-Diaconis: for any finite irreducible Markov chain and any initial state, there exists a strong uniform time T with P(T>k|X0=a)=s_a(k).
    Invoked in Section 3 to build the block sequence t_i; this is an external standard result.
  • domain assumption Known i.i.d. completion-time bounds for Push, Pull, Push-Pull and Flood on Erdős-Rényi graphs (Clementi et al., Doerr and Kostrygin, Daknama).
    The reduction transfers these external bounds; the paper does not re-derive them.
  • domain assumption Gallo's CFTP theorem: a process with the renewal hazard condition (3) can be perfectly simulated by a coalescing time theta_0 that is almost surely finite and geometric.
    Used in Section 4.2 to obtain stationary times for the renewal edge process.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Rumors on evolving graphs through stationary times." pith.science (2026). https://pith.science/paper/CMBFLKAG

@misc{pith2026250604386,
  author       = {Pith},
  title        = {Pith review of: Rumors on evolving graphs through stationary times},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CMBFLKAG}},
  note         = {Machine review of arXiv:2506.04386}
}
abstract

We study rumor spreading in dynamic random graphs. Starting with a single informed vertex, the information flows until it reaches all the vertices of the graph (completion), according to the following process. At each step $k$, the information is propagated to neighbors of the informed vertices, in the $k$-th generated random graph. The way this information propagates from vertex to vertex at each step will depend on the ``protocol". We provide a method based on strong stationary times to study the completion time when the graphs are Markovian time dependent, using known results of the literature for independent graphs. The concept of strong stationary times is then extended to non-Markovian Dynamics using coupling from the past algorithms. This allows to extend results on completion times for non-Markov dynamics

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter edition editor howpublished institution journal key language month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sen...

    work page

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize ":" * " " *...

    work page

  3. [3]

    & Diaconis, P

    Aldous, D. & Diaconis, P. (1987). Strong uniform times and finite random walks. Advances in Applied Mathematics 8(1), 69--97

    work page 1987

  4. [4]

    & Panconesi, A

    Chierichetti, F., Lattanzi, S. & Panconesi, A. (2010). Almost tight bounds on rumour spreading by conductance. In: In Proceedings of 42nd ACM STOC, ACM, New York

    work page 2010

  5. [5]

    & Silvestri, R

    Clementi, A., Crescenzi, P., Doerr, C., Fraigniaud, P., Pasquale, F. & Silvestri, R. (2016). Rumor spreading in random evolving graphs. Random Structures & Algorithms 48(2), 290--312

    work page 2016

  6. [6]

    & Silvestri, R

    Clementi, A., Massi, C., Monti, A., Pasquele, F. & Silvestri, R. (2010). Flooding time of edge-markovian evolving graphs. SIAM journal on discrete mathematics 24(4), 1694--1712

    work page 2010

  7. [7]

    & Ferrari, P

    Comets, F., Fern \'a ndez, R. & Ferrari, P. A. (2002). Processes with long memory: regenerative construction and perfect simulation. Ann. Appl. Probab. 12(3), 921--943. ://dx.doi.org/10.1214/aoap/1031863175

    arXiv 2002

  8. [8]

    Daknama, R. (2017). Pull and push-pull in random evolving graphs. arXiv:1801.00316

    work page Pith review arXiv 2017

Show all 16 references
  1. [9]

    & Kostrygin, A

    Doerr, B. & Kostrygin, A. (2017). Randomized rumor spreading revisited. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), vol. 80

    2017

  2. [10]

    & Upfal, E

    Feige, U., Peleg, D., Raghavan, P. & Upfal, E. (1990). Randomized broadcast in networks. Random Struct Algorithms 1, 447--460

    1990

  3. [11]

    & Grimmett, G

    Frieze, A. & Grimmett, G. (1985). The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics 10, 57--77

    1985

  4. [12]

    Gallo, S. (2011). Chains with unbounded variable length memory: perfect simulation and visible regeneration scheme. Adv. Appl. Prob. 43(3)

    2011

  5. [13]

    & Garcia, N

    Gallo, S. & Garcia, N. L. (2013). Perfect simulation for locally continuous chains of infinite order. Stochastic Process. Appl. 123(5), 3877--3902

    2013

  6. [14]

    Levin, D. A. & Peres, Y. (2017). Markov chains and mixing times, vol. 107. American Mathematical Soc

    2017

  7. [15]

    Propp, J. G. & Wilson, D. B. (1996). Exact sampling with coupled M arkov chains and applications to statistical mechanics. In: Proceedings of the S eventh I nternational C onference on R andom S tructures and A lgorithms ( A tlanta, GA , 1995) , vol. 9

    1996

  8. [16]

    & Stauffer, A

    Sauerwald, T. & Stauffer, A. (2011). Rumor spreading and vertex expansion on regular graphs. In: In Proceedings of 22nd ACM-SIAM SODA, SIAM, San Francisco, California, USA, January 23–25

    2011

Pith tools

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