Threshold-Driven Streaming Graph: Expansion and Rumor Spreading

Andrea Clementi; Emanuele Natale; Flora Angileri; Isabella Ziccardi; Michele Salvi

REVIEW 2 major objections 5 minor 54 references

Threshold-Driven Streaming Graph: Expansion and Rumor Spreading

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Under streaming node churn, a threshold-based link protocol keeps every snapshot an almost-full expander, and rumor spreading completes in O(log n) rounds.

desk verdict Strong expansion results for a new threshold/churn model, but Theorem 1.2 needs a real proof of the bootstrap, not just a sketch. read the letter →

arxiv 2507.23533 v1 pith:4YANH6A7 submitted 2025-07-31 cs.DC math.PR

Flora Angileri , Andrea Clementi , Emanuele Natale , Michele Salvi , Isabella Ziccardi This is my paper

classification cs.DCmath.PR MSC 68W1568W2005C80

keywords threshold-drivenstreaminggraphexpandernodechurnRAESrumorspreadingconductanceboundeddegreemodel

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 tries to establish that a simple threshold-driven link protocol keeps a peer-to-peer-style network well connected even when the vertex population itself streams, with one node joining and one node leaving every round. Specifically, it analyzes TSG(n,d,c), in which each vertex maintains d outgoing connection requests and accepts incoming requests only up to a cd cap, and proves that every snapshot after round 2n is, with high probability, an almost-full expander: an induced subgraph on n − O(log n) vertices is an expander, and every vertex subset of size at least β log n has constant conductance. It then proves that the same expansion makes rumor spreading fast: if a source joins at or after round 2n, both push and pull inform n − O(log n) vertices within O(log n) rounds. A reader should care because bounded-degree, decentralized topologies that survive node churn are exactly what unstructured peer-to-peer networks need, and this paper shows that a local threshold rule alone can supply them with near-optimal message overhead.

What carries the argument

The load-bearing object is Lemma 4.1, a near-product bound on the joint distribution of link destinations: for any set R of requests and any target set P, the probability that every request in R lands in P is at most (220|P|/(n−1))^{|R|}. This is what controls the correlations created by the threshold acceptance rule, where one rejected request can cascade into future requests. The surrounding machinery is a queue argument: Lemmas 4.2–4.4 show that the number of pending requests stays O(log n) with high probability and that each request is pending only O(1) rounds in expectation, bounding message load at O(log n) per round. Expansion then follows by a union bound over small subsets and an age-order argument for large subsets, and the expander subgraph is built from vertices with no pending requests.

What would settle it

Run the TSG(n,d,c) process for many independent rounds and, at each t ≥ 2n, measure the conductance of every subset of size β log n and the size of the largest induced expander subgraph. The theorem predicts constant conductance for all such subsets and an induced expander on n − O(log n) vertices; if a constant fraction of rounds showed a subset of size β log n with conductance below 1/(10(c+1)d), or more than O(log n) vertices outside the expander, the claim would be refuted. A targeted test of the model assumption is to substitute a link manager that returns only vertices from a fixed half of the population: the near-product bound already fails in that variant, and the same empirical measurements should show the expansion property breaking.

Watch

Extended reading notes

Core claim

The central claim is that the original RAES acceptance rule—reject all incoming requests in a round whenever accepting them would exceed a cd in-degree cap—does not break down under streaming node churn. For any round t ≥ 2n, the snapshot G_t generated by TSG(n,d,c) has, with high probability, an induced expander subgraph on all but O(log n) vertices and constant conductance for every subset of size at least β log n; this is Theorem 1.1. As a consequence, Theorem 1.2 states that push or pull rumor spreading from a source that joins at round t_s ≥ 2n reaches n − O(log n) vertices within O(log n) rounds. The O(log n) slack is inherent to the model, because a freshly joined vertex may stay isolated for o(log n) rounds with non-negligible probability, so the broadcast target cannot reasonably be all n vertices.

Load-bearing premise

The entire analysis assumes that every connection request targets a destination chosen independently and uniformly at random among the currently alive vertices; if a link manager returned biased or correlated destinations, the near-product bound and the expansion and rumor-spreading conclusions would no longer be guaranteed.

Editorial extensions

If this is right

Every snapshot after round 2n is, with high probability, an expander on all but O(log n) vertices, so distributed tasks that need constant conductance can run on a network whose membership changes completely every n rounds.
Push and pull rumor spreading from a late-joining source finish in O(log n) rounds and inform all but O(log n) vertices, giving a logarithmic broadcast bound in a churning bounded-degree model.
The number of link-manager calls per round is O(log n) with high probability and constant in expectation, so maintaining the expander does not congest the network.
Each vertex makes O(log n) total link-manager calls over its lifetime with high probability and O(1) in expectation, so per-node work stays small.
The n − O(log n) broadcast target is tight: fresh vertices can stay isolated for o(log n) rounds, so no protocol of this type can guarantee informing the last few arrivals immediately.

Reading between the lines

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

The cycle decomposition used to prove Lemma 4.1, where a request alternates between a stable connected phase and a geometric rejection phase, looks portable to Poisson node churn with random lifetimes, where snapshot size itself fluctuates; the paper explicitly conjectures this extension.
The proof's real requirement is that no target set P receives too much probability mass—bounded by O(|P|/n) per request—so a link manager with mild bias over a large support might preserve the expansion bounds with larger constants, even though the paper only analyzes the uniform case.
Because a logarithmic informed set is shown to stay stable for Θ(log^2 n) rounds, a self-stabilizing variant that resets corrupted links while preserving the queue-halving property could plausibly recover from arbitrary bad states in polylogarithmic time; the paper raises this as an open direction.
A protocol that gives each new vertex one guaranteed initial connection, or lets it pull from an already-informed neighbor on entry, could plausibly reduce the uninformed slack from O(log n) to o(log n), closing the only gap left open by Theorem 1.2.

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.

Desk Editor's Note

read the letter

Nice read overall. The paper introduces TSG(n,d,c), the streaming node-churn model with RAES's threshold acceptance, and proves that every snapshot is a good expander w.h.p. The expansion part is the real substance. Lemma 4.1, bounding the joint distribution of link destinations by a product form up to constant factor, is a genuine technical step beyond both the static RAES analysis [10] and the unbounded-degree churn model [12]. The queue control (Lemmas 4.2–4.4) is clean and gives optimal message work. Theorems 5.1 (a) and (b) rest on detailed multi-step proofs; I did not find a load-bearing error there, just the usual 'choose c,d large enough' constants.

The soft spot is Theorem 1.2. The proof sketch in Section 6.2 is exactly that: a sketch. Lemma 6.3 shows that w.h.p. the source lands in a stable connected component of size Ω(log n) inside H_ts minus OLD, but it does not show that Ω(log n) nodes actually get informed in O(log n) rounds. The paper jumps from 'connected component of size β log n' to 'now apply the expansion argument'. I disagree with the stress-test's specific quantitative point: on a bounded-degree path of length L, push and pull take O(L) rounds, not Θ(L log L), because each boundary step succeeds with constant probability. So the component doesn't need to be an expander for the bootstrap. But the paper still owes the reader the easy geometric argument: in a connected graph with maximum degree Δ=O(1), starting from one informed node, the informed set reaches size L in O(Δ L) rounds w.h.p., so L=Θ(log n) gives O(log n). They didn't include it, and as written the transition in Lemma 6.3 to the expansion phase is not demonstrated.

There are also typos and small garbles in Lemma 4.1's proof (e.g., the comment about 'may not be in V_sj' reads backwards), which reduce confidence even though the high-level structure of that lemma is sound. The citation pattern is fair: [10,12] are prior work, not circular, and Lemma 4.1 is new. No fitted parameters.

Who is this for? Researchers in distributed algorithms and random dynamic graphs. The expansion theorem alone is a solid contribution. With a completed bootstrap proof, the rumor-spreading result would be a strong paper. As it stands, it should go to peer review, with a request for a full proof of Theorem 1.2 and a cleaned-up Lemma 4.1. I would not desk-reject it.

Referee Report

2 major / 5 minor

Summary. The manuscript introduces the Threshold-Driven Streaming Graph model TSG(n,d,c), which combines the streaming node-churn process with the threshold-based RAES edge-formation rule from prior work. The main results are: (i) for every round t ≥ 2n, the snapshot G_t is w.h.p. an expander in the sense that every vertex subset of size at least β log n has constant conductance and there is an induced expander subgraph on n − O(log n) vertices; and (ii) push or pull rumor spreading from a source joining at time t_s ≥ 2n informs n − O(log n) vertices within O(log n) rounds. The technical core is a joint-distribution lemma (Lemma 4.1) that controls correlations among accepted link destinations, a queue bound (Lemma 4.2) for the number of pending requests, expansion proofs for small and large subsets (Lemmas 5.2 and 5.3), and a proof sketch for the rumor-spreading bootstrap (Lemma 6.3) and its use of the static conductance-based analysis.

Significance. If both theorems are correct, the expansion half is a substantial contribution: it extends the static RAES analysis to a dynamic node-churn model while keeping bounded degree, and it gives near-optimal communication costs (O(log n) pending requests per round, w.h.p.). Lemma 4.1 appears to be a genuinely new technical tool, and the queue analysis in Section 4.2 is nontrivial. The rumor-spreading claim is a natural and important application, but the current proof of Theorem 1.2 is only a sketch and contains a load-bearing gap: the bootstrap lemma does not prove what it states. The expansion theorem alone may be publishable, but the paper as submitted claims both results and needs a rigorous treatment of the bootstrap before the rumor-spreading theorem can be accepted.

major comments (2)

[Section 6.2, Lemma 6.3 and the paragraph following its proof] Lemma 6.3 states that within T' = O(log n) rounds there are β log n informed nodes, but its proof only establishes that the source w.h.p. belongs to a connected subgraph of size at least β log n that remains connected for Θ(log^2 n) rounds. Connectivity alone does not imply O(log n) w.h.p. spreading: on a path component of length Θ(log n), push and pull advance the front by one vertex with constant probability per round, so a high-probability bound requires Ω(log^2 n) rounds, not O(log n). The proof also does not show that the component inherits expansion from H_t after deleting OLD; Lemma 5.2 controls expansion in the full snapshot G_t, but all boundary vertices of a subset of that component could lie outside the component or in OLD. The sentence 'Finally, thanks to Lemma 6.3, we can apply the expansion argument' is therefore circular: Lemma 6.3 was supposed to produce the informed set, yet its proof never analyzes the rumor protocol or the informed set. This gap is load-bearing for Theorem 1.2.
[Section 6.2, 'The analysis on the TSG model'] The proof after the bootstrap invokes the proof argument of Theorem 6.2, which is a static-graph statement requiring a fixed connected graph with constant conductance and a bounded degree ratio. The TSG snapshots are not fixed: vertices leave, new vertices join, and the graph changes every round. The text asserts in one sentence that a logarithmic informed set 'dominates' the impact of edge deletions over a logarithmic window, but it does not supply a formal coupling or a round-by-round argument showing that the conductance-based expansion analysis applies to the evolving snapshots and to the evolving set of informed nodes. Assuming the bootstrap were fixed, this dynamic adaptation would still need a detailed proof rather than an appeal to the static theorem.

minor comments (5)

[Section 4.2, proof of Lemma 4.2, Eq. (23)] The displayed inclusion writes '|Q_t| ≤ 100 log n', dropping the factor (cd)^2 that appears in the lemma statement and in the preceding displayed inequality; it should be 100(cd)^2 log n.
[Theorem 5.1 statement] The statement says 'α = α(d) sufficiently large integers', but conductance is bounded above by 1 and the proofs (Lemmas 5.2–5.4) yield a bound of order 1/((c+1)d); the wording should be corrected to 'α = α(c,d) ∈ (0,1)' or similar.
[References [16] and [17]] References [16] and [17] are the same paper by Chierichetti, Giakkoupis, Lattanzi, and Panconesi; the duplicate should be merged and the citation in Section 6.2 made consistent.
[Theorem 1.2 statement and Section 6.1] There is a typo in the theorem statement ('inform at leastn−O(log n)') and 'uniformed' should be 'uninformed' in the description of the pull protocol in Section 6.1.
[Section 6.2, Lemma 6.3 and Lemma 5.2] Lemma 6.3 uses β log n as the bootstrap target, while Lemma 5.2 guarantees expansion only for sets of size at least 2β log n; the proof never reconciles this factor-of-two gap, even though the gap is presumably fixable by adjusting constants.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: expansion and rumor bounds follow from the model definition and an external rumor-spreading theorem; self-citations are contextual and the only real weakness is an unproven bootstrap step, which is a correctness gap rather than circularity.

full rationale

The core derivation is from the TSG(n,d,c) definition. Lemma 4.1 bounds joint destination probabilities directly from the uniform random link-manager assumption in Definition 3.3(b) and the threshold acceptance rule in Definition 3.3(c); it is not assumed as an input. Lemmas 5.2-5.4 derive vertex expansion and the n-O(log n) expander subgraph from Lemma 4.1 and the queue bound Lemma 4.2, with no fitted parameters and no data subset being predicted. Citations [10] and [12] supply the RAES protocol and the streaming churn model, but the new combined-model analysis does not reduce to those results; no uniqueness claim or ansatz is imported from self-citation. The rumor-spreading proof invokes Theorem 6.2 from the external work of Chierichetti et al., not from the authors' own prior papers, so that step is independent support. One non-circular weakness must be flagged, as the reviewing rule requires: Lemma 6.3 in Section 6.2 states that within O(log n) rounds there are beta log n informed nodes, but its proof only establishes that the source w.h.p. connects to a connected subgraph of H_{ts} of size at least beta log n that survives Theta(log^2 n) rounds. The text then says 'thanks to Lemma 6.3, we can apply the expansion argument' to informed sets of size >= beta log n. Connectivity of a component containing the source does not by itself imply that push/pull has produced beta log n informed vertices in O(log n) rounds, especially because H_{ts} minus OLD need not inherit the small-set expansion of H_{ts} and a path-like component would require Theta(log n log log n) rounds. This is an omitted proof or correctness gap in the bootstrap, not an equivalence by construction or a fitted-input-called-prediction step; therefore it does not raise the circularity score beyond negligible.

Assumptions & free parameters 4 free parameters · 5 assumptions · 1 invented entities

The central results rest on the streaming churn model, uniform random sampling via the link manager, the threshold acceptance rule, and standard concentration tools. These are model definitions and external theorems, not fitted parameters. The constants c, d, β are existential choices, not data fits.

free parameters (4)

c = sufficiently large constant
Threshold multiplier; controls full-vertex bound n/c and rejection probability. Chosen via inequalities, not fitted to data.
d = sufficiently large constant
Out-degree; must exceed constants such as 43 and 7 in expansion union bounds. Chosen via inequalities, not fitted to data.
beta = 100(cd)^2
Defined in Lemma 5.2 as the log-size threshold for good expansion; depends on c and d.
alpha = not specified (typo in statement)
Conductance lower bound in Theorem 5.1; the statement says 'sufficiently large integers' but conductance is at most 1. Proofs give Ω(1) conductance via vertex expansion.

assumptions (5)

domain assumption Streaming node churn: each round a new vertex joins and the vertex that joined n rounds ago leaves (Definition 3.2).
Defines the sliding-window dynamics; load-bearing for all snapshot arguments.
domain assumption Link manager: every request targets a destination chosen independently and uniformly at random in V_t \ {v} (Definition 3.3(b)).
Uniform independent sampling is essential for Lemma 4.1's product-form bound.
domain assumption Threshold acceptance rule: a vertex accepts all requests in a round iff its in-degree after accepting stays ≤ cd, else rejects all (Definition 3.3(c)).
Defines the bounded-degree mechanism; analyses of full vertices and rejection probability use it.
standard math External theorem: on a bounded-degree graph with conductance φ, push/pull spread a rumor to all nodes in O(log n / φ) rounds (Theorem 6.2, from [17]).
The paper uses this static-graph result and its proof argument as the basis for Theorem 1.2.
standard math Standard concentration inequalities: Chernoff, Hoeffding, method of bounded differences (Appendix A).
Used throughout Lemmas 4.2, 4.4, 5.2, 5.3.

invented entities (1)

Link manager
purpose: Provides uniform random destination sampling on demand for link requests.
Modeling abstraction analogous to DNS seeds in Bitcoin; not empirically verified and no falsifiable prediction attached.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Threshold-Driven Streaming Graph: Expansion and Rumor Spreading." pith.science (2026). https://pith.science/paper/4YANH6A7

@misc{pith2026250723533,
  author       = {Pith},
  title        = {Pith review of: Threshold-Driven Streaming Graph: Expansion and Rumor Spreading},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4YANH6A7}},
  note         = {Machine review of arXiv:2507.23533}
}

abstract

A randomized distributed algorithm called RAES was introduced in [Becchetti et al., SODA 2020] to extract a bounded-degree expander from a dense $n$-vertex expander graph $G = (V, E)$. The algorithm relies on a simple threshold-based procedure. A key assumption in [Becchetti et al., SODA 2020] is that the input graph $G$ is static - i.e., both its vertex set $V$ and edge set $E$ remain unchanged throughout the process - while the analysis of RAES in dynamic models is left as a major open question. In this work, we investigate the behavior of RAES under a dynamic graph model induced by a streaming node-churn process (also known as the sliding window model), where, at each discrete round, a new node joins the graph and the oldest node departs. This process yields a bounded-degree dynamic graph $\mathcal{G} =\{ G_t = (V_t, E_t) : t \in \mathbb{N}\}$ that captures essential characteristics of peer-to-peer networks -- specifically, node churn and threshold on the number of connections each node can manage. We prove that every snapshot $G_t$ in the dynamic graph sequence has good expansion properties with high probability. Furthermore, we leverage this property to establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor spreading protocols over the dynamic graph $\mathcal{G}$.

Figures

Figures reproduced from arXiv: 2507.23533 by the authors.

**Figure 1.** Variables W0, W1, . . . , WF and Z0, Z1, . . . , ZF in the time interval {tℓ , . . . , sℓ} referring to the behavior of the request rℓ . Denote for simplicity by C the event on which we are conditioning: C = ∩h:ah⩽sℓ {rh ah −→ P}. Notice that, for any f ⩾ 1, it holds |W0| + |W1| + · · · + |Wf−1| = wf − tℓ , where wf is random. STEP 4: Proof of the worst-case bound: comparison with S1 and S2. Consider now the followi… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

54 extracted references · 53 canonical work pages

[10]

Becchetti, A

L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan. Finding a bounded-degree expander inside a dense one. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1320–1336. SIAM, 2020. 30

work page 2020
[12]

Becchetti, A

L. Becchetti, A. Clementi, F. Pasquale, L. Trevisan, and I. Ziccardi. Expansion and flooding in dynamic random networks with node churn. Random Structures & Algorithms , 63(1):61–101, 2023

work page 2023
[1]

Albrecht, S

J. Albrecht, S. Andreina, F. Armknecht, G. Karame, G. Marson, and J. Willingmann. Larger- scale nakamoto-style blockchains don’t necessarily offer better security. In 2024 IEEE Sympo- sium on Security and Privacy (SP) , pages 2161–2179. IEEE, 2024

work page 2024
[2]

Allen-Zhu, A

Z. Allen-Zhu, A. Bhaskara, S. Lattanzi, V. Mirrokni, and L. Orecchia. Expanders via local edge flips. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 259–269. Society for Industrial and Applied Mathematics, 2016

work page 2016
[3]

Altisen, S

K. Altisen, S. Devismes, S. Dubois, and F. Petit. Introduction to distributed self-stabilizing algorithms. Springer Nature, 2022

work page 2022
[4]

Augustine, G

J. Augustine, G. Pandurangan, and P. Robinson. Distributed algorithmic foundations of dynamic networks. ACM SIGACT News , 47(1):69–98, 2016

work page 2016
[5]

Augustine, G

J. Augustine, G. Pandurangan, P. Robinson, S. Roche, and E. Upfal. Enabling robust and efficient distributed computation in dynamic peer-to-peer networks. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 350–369. IEEE, 2015

work page 2015
[6]

Augustine, G

J. Augustine, G. Pandurangan, P. Robinson, and E. Upfal. Towards robust and efficient computation in dynamic peer-to-peer networks. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, page 551–569, USA, 2012. Society for Industrial and Applied Mathematics

work page 2012

Show all 54 references

[7]

Awerbuch and C

B. Awerbuch and C. Scheideler. The hyperring: A low-congestion deterministic data structure for distributed environments. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’04, page 318–327, USA, 2004. Society for Industrial and Ap- plied ...

2004
[8]

Bansal, O

N. Bansal, O. Svensson, and L. Trevisan. New notions and constructions of sparsification for graphs and hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 910–928. IEEE, 2019

2019
[9]

Baumann, B

A. Baumann, B. Fabian, and M. Lischke. Exploring the bitcoin network. WEBIST (1) , 2014(369-374):3, 2014

2014
[11]

Becchetti, A

L. Becchetti, A. Clementi, F. Pasquale, L. Trevisan, and I. Ziccardi. Expansion and flooding in dynamic random networks with node churn. In 41st IEEE International Conference on Distributed Computing Systems, ICDCS 2021, Washington DC, USA, July 7-10, 2021 , pages 976–986. IEEE, 2021

2021
[13]

Borassi, A

M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, and M. Zadimoghaddam. Sliding window algorithms for k-clustering problems. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on...

2020
[14]

Boukerche and A

A. Boukerche and A. Darehshoorzadeh. Opportunistic routing in wireless networks: Models, algorithms, and classifications. ACM Computing Surveys (CSUR) , 47(2):1–36, 2014

2014
[15]

Braverman, H

V. Braverman, H. Lang, K. D. Levin, and M. Monemizadeh. Clustering problems on sliding windows. In R. Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, V A, USA, January 10-12, 2016 , pages 1374–1390....

2016
[17]

Chierichetti, G

F. Chierichetti, G. Giakkoupis, S. Lattanzi, and A. Panconesi. Rumor spreading and conduc- tance. J. ACM, 65(4), Apr. 2018

2018
[18]

Clementi, P

A. Clementi, P. Crescenzi, C. Doerr, P. Fraigniaud, M. Isopi, A. Panconesi, F. Pasquale, and R. Silvestri. Rumor spreading in random evolving graphs. In European symposium on algorithms, pages 325–336. Springer, 2013

2013
[19]

Clementi, P

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

2016
[20]

Clementi, E

A. Clementi, E. Natale, and I. Ziccardi. Parallel load balancing on constrained client-server topologies. Theor. Comput. Sci. , 895:16–33, 2021

2021
[21]

A. E. F. Clementi, C. Macci, A. Monti, F. Pasquale, and R. Silvestri. Flooding time of edge- markovian evolving graphs. SIAM Journal on Discrete Mathematics , 24(4):1694–1712, 2010

2010
[22]

A. E. F. Clementi, A. Monti, F. Pasquale, and R. Silvestri. Information spreading in stationary markovian evolving graphs. IEEE Trans. Parallel Distrib. Syst. , 22(9):1425–1432, 2011

2011
[23]

Cooper, M

C. Cooper, M. E. Dyer, and C. S. Greenhill. Sampling regular graphs and a peer-to-peer network. Comb. Probab. Comput. , 16(4):557–593, 2007

2007
[24]

Cooper, R

C. Cooper, R. Klasing, and T. Radzik. A randomized algorithm for the joining protocol in dynamic distributed networks. Theor. Comput. Sci. , 406(3):248–262, 2008

2008
[25]

M. S. Crouch, A. McGregor, and D. Stubbs. Dynamic graphs in the sliding-window model. In Algorithms–ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, Septem- ber 2-4, 2013. Proceedings 21 , pages 337–348. Springer, 2013. 31

2013
[26]

Cruciani and F

A. Cruciani and F. Pasquale. Brief announcement: Dynamic graph models for the bitcoin p2p network: Simulation analysis for expansion and flooding time. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems , pages 335–340. Springer, 2022

2022
[27]

Cruciani and F

A. Cruciani and F. Pasquale. Dynamic graph models inspired by the bitcoin network-formation process. In Proceedings of the 24th International Conference on Distributed Computing and Networking, pages 125–134, 2023

2023
[28]

Delgado-Segura, S

S. Delgado-Segura, S. Bakshi, C. P´ erez-Sol` a, J. Litton, A. Pachulski, A. Miller, and B. Bhat- tacharjee. Txprobe: Discovering bitcoin’s network topology using orphan transactions. In In- ternational Conference on Financial Cryptography and Data Security, pages 550–566. Spr...

2019
[29]

Demers, D

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proceedings of the sixth annual ACM Symposium on Principles of distributed computing , pages 1–12, 1987

1987
[30]

E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643–644, 1974

1974
[31]

D. P. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009

2009
[32]

Duchon and R

P. Duchon and R. Duvignau. Local update algorithms for random graphs. In A. Pardo and A. Viola, editors, LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings , volume 8392 of Lecture Notes in Computer S...

2014
[33]

Dutta, G

C. Dutta, G. Pandurangan, R. Rajaraman, and Z. Sun. Information spreading in dynamic networks. arXiv preprint arXiv:1112.0384 , 2011

2011 arXiv
[34]

Els¨ asser and T

R. Els¨ asser and T. Sauerwald. Cover time and broadcast time. In26th International Symposium on Theoretical Aspects of Computer Science (2009), pages 373–384. Schloss Dagstuhl–Leibniz- Zentrum f¨ ur Informatik, 2009

2009
[35]

Feige, D

U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures & Algorithms , 1(4):447–460, 1990

1990
[36]

Giakkoupis

G. Giakkoupis. Expanders via local edge flips in quasilinear time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 64–76, 2022

2022
[37]

Giakkoupis, T

G. Giakkoupis, T. Sauerwald, and A. Stauffer. Randomized rumor spreading in dynamic graphs. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II 41 , pages 495–507. Springer, 2014

2014
[38]

Gupta and G

A. Gupta and G. Pandurangan. Fully-distributed construction of byzantine-resilient dynamic peer-to-peer networks. CoRR, abs/2506.04368, 2025

2025 arXiv
[39]

Harchol-Balter, T

M. Harchol-Balter, T. Leighton, and D. Lewin. Resource discovery in distributed networks. In Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing , pages 229–237, 1999. 32

1999
[40]

Hoory, N

S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society , 43(4):439–561, 2006

2006
[41]

Jacob, A

R. Jacob, A. Richa, C. Scheideler, S. Schmid, and H. T¨ aubig. A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing , PODC ’09, page 131–140, New York, NY, USA, 2009. Asso...

2009
[42]

R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In Proceedings 41st Annual Symposium on Foundations of Computer Science , pages 565–574. IEEE, 2000

2000
[43]

F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing , STOC ’10, page 513–522, New York, NY, USA, 2010. Association for Computing Machinery

2010
[44]

Kuhn and R

F. Kuhn and R. Oshman. Dynamic networks: Models and algorithms. SIGACT News , 42(1):82–96, Mar. 2011

2011
[45]

Law and K.-Y

C. Law and K.-Y. Siu. Distributed construction of random expander networks. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications (INFOCOM 2003), volume 3, pages 2133–2143. IEEE, 2003

2003
[46]

Mahlmann and C

P. Mahlmann and C. Schindelhauer. Peer-to-peer networks based on random transformations of connected regular undirected graphs. In Proceedings of the Seventeenth Annual ACM Sym- posium on Parallelism in Algorithms and Architectures , SPAA ’05, page 155–164, New York, NY, USA, ...

2005
[47]

O. Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Math- ematics, 12(4):239–280, 2016

2016
[48]

Mitzenmacher and E

M. Mitzenmacher and E. Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press, 2017

2017
[49]

Nakamoto

S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/ bitcoin.pdf, 2008

2008
[50]

Neudecker, P

T. Neudecker, P. Andelfinger, and H. Hartenstein. Timing analysis for inferring the topology of the bitcoin peer-to-peer network. In 2016 Intl IEEE Conferences on Ubiquitous Intel- ligence & Computing, Advanced and Trusted Computing, Scalable Computing and Commu- nications, Cl...

2016
[51]

Pandurangan, P

G. Pandurangan, P. Raghavan, and E. Upfal. Building low-diameter peer-to-peer networks. IEEE Journal on selected areas in communications, 21(6):995–1002, 2003. Preliminary version in FOCS’01

2003
[52]

Pandurangan and A

G. Pandurangan and A. Trehan. Xheal: A localized self-healing algorithm using expanders. Distrib. Comput. , 27(1):39–54, Feb. 2014

2014
[53]

Stutzbach and R

D. Stutzbach and R. Rejaie. Understanding churn in peer-to-peer networks. In Proceedings of the 6th ACM SIGCOMM conference on Internet measurement , pages 189–202, 2006. 33

2006
[54]

Van Renesse, Y

R. Van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. In Middleware’98: IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing, pages 55–70. Springer, 1998

1998
[55]

A. Yeow. Global Bitcoin Nodes Distribution. https://bitnodes.io/. Accessed: 2020-07-15. A Concentration Inequalities Definition A.1 (Lipschitz property, [31]). A real-valued function f (x1, . . . , xn) satisfies the Lips- chitz property with constants di, i ∈ [n], if f (x) − f...

2020

Pith tools

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

[1] [10]

Becchetti, A

L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan. Finding a bounded-degree expander inside a dense one. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1320–1336. SIAM, 2020. 30

work page 2020

[2] [12]

Becchetti, A

L. Becchetti, A. Clementi, F. Pasquale, L. Trevisan, and I. Ziccardi. Expansion and flooding in dynamic random networks with node churn. Random Structures & Algorithms , 63(1):61–101, 2023

work page 2023

[3] [1]

Albrecht, S

J. Albrecht, S. Andreina, F. Armknecht, G. Karame, G. Marson, and J. Willingmann. Larger- scale nakamoto-style blockchains don’t necessarily offer better security. In 2024 IEEE Sympo- sium on Security and Privacy (SP) , pages 2161–2179. IEEE, 2024

work page 2024

[4] [2]

Allen-Zhu, A

Z. Allen-Zhu, A. Bhaskara, S. Lattanzi, V. Mirrokni, and L. Orecchia. Expanders via local edge flips. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 259–269. Society for Industrial and Applied Mathematics, 2016

work page 2016

[5] [3]

Altisen, S

K. Altisen, S. Devismes, S. Dubois, and F. Petit. Introduction to distributed self-stabilizing algorithms. Springer Nature, 2022

work page 2022

[6] [4]

Augustine, G

J. Augustine, G. Pandurangan, and P. Robinson. Distributed algorithmic foundations of dynamic networks. ACM SIGACT News , 47(1):69–98, 2016

work page 2016

[7] [5]

Augustine, G

J. Augustine, G. Pandurangan, P. Robinson, S. Roche, and E. Upfal. Enabling robust and efficient distributed computation in dynamic peer-to-peer networks. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 350–369. IEEE, 2015

work page 2015

[8] [6]

Augustine, G

J. Augustine, G. Pandurangan, P. Robinson, and E. Upfal. Towards robust and efficient computation in dynamic peer-to-peer networks. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, page 551–569, USA, 2012. Society for Industrial and Applied Mathematics

work page 2012