Pith. sign in

REVIEW 4 major objections 4 minor 2 cited by

Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks

T0 review · 4 major / 4 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 fully distributed protocol maintains a constant-degree expander overlay while Byzantine nodes and continuous churn are present.

desk verdict First credible attempt at maintaining a bounded-degree expander under both stochastic churn and many Byzantine nodes, but the proof of the core theorem is not yet rigorous: the base case is hand-waved and the induction oversimplifies edge persistence. read the letter →

arxiv 2506.04368 v2 pith:A3HWWVOH submitted 2025-06-04 cs.DC

Aayush Gupta , Gopal Pandurangan This is my paper
classification cs.DC MSC 68M1468W1505C80
keywords peer-to-peernetworksByzantinefaulttoleranceexpandergraphsdistributedalgorithmsdynamicrandomwalkschurnoverlay
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 claims that a randomized, fully distributed protocol can build and maintain a sparse overlay network with high expansion even while nodes continuously join and leave and a large number of them are Byzantine, i.e., adversarially malicious. Previous algorithms for agreement, leader election, and storage in dynamic P2P networks assumed such an expander was already supplied each round; this protocol is meant to be the component that actually supplies it. If the claim holds, it closes the gap between algorithms that need an expander and realistic networks that must construct one under churn and attack, and it does so with only polylogarithmic communication and computation per node per round.

What carries the argument

The carrying mechanism is the Byzantine Random Walk Protocol (Algorithm 3), adapted from the static setting. Each honest node launches O($log^{3}$ n) tokens per phase; each token walks c log n steps, and a token that survives is verified and returned, via the reverse path, to its source, which then uses verified tokens to form new connections. Neighbors that send more than cap tokens per round are blacklisted, which bounds the influence of Byzantine flooding. The protocol refreshes connections every η log n rounds, a phase, so deletions do not permanently degrade expansion. The Byzantine Random Walk Theorem (Theorem 1), assuming a static core of honest nodes within a phase, guarantees that most tokens from most core nodes mix almost uniformly inside the core, giving the near-random samples that drive new edges.

What would settle it

Run the protocol under the paper's stochastic churn model and, at every phase boundary, compute the conductance of the largest honest subgraph after deleting Byzantine nodes; the theorem predicts a fixed constant lower bound for all t ≥ Θ(√n), so a phase where the honest core's conductance drops below any fixed constant with non-negligible probability would refute it. On the proof side, the base case is the weakest spot: writing out Lemma 9's easy-to-show step would either establish or refute that the honest subgraph at t1 = Θ(√n) is an expander, and a legal churn trajectory where it is not would break the induction regardless of later phases.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2: for any time t ≥ Θ(√n), with probability at least 1 − 1/n^Ω(1), the P2P Construction Protocol maintains a bounded-degree graph G_t containing a subgraph of at least (1−o(1))|V_t| honest nodes that is a constant-degree expander, while tolerating up to o(|V_t|/log(|V_t|)) Byzantine nodes. Once the network stabilizes at t ≥ 3n, the guaranteed subgraph has size (1−o(1))n and the protocol tolerates o(n/log n) Byzantine nodes. The protocol is fully distributed in the sense that each node knows only its neighbors and a rough estimate of n, and each honest node processes and sends only O(polylog n) bits per round.

Load-bearing premise

The load-bearing premise is that early on, when the network first reaches size on the order of the square root of its stable size, the honest nodes already form a sparse, well-connected graph with high expansion; the paper asserts this in Lemma 9 with an it is easy to show argument, and if this base case is not true the later induction cannot start.

Editorial extensions

If this is right

  • If the construction holds, algorithms for Byzantine agreement, Byzantine leader election, and storage and search in dynamic P2P networks can run on top of the maintained expander rather than assuming one is given.
  • The guarantee is maintained continuously at every phase boundary, not only after stabilization: from t = Θ(√n) onward the honest expander subgraph has size (1−o(1)) of the network.
  • Because each honest node only sends and processes polylogarithmic bits per round, the protocol is scalable enough to be used as a building block in large decentralized systems.
  • The Byzantine tolerance of o(n/log n) is within a logarithmic factor of the paper's conjectured barrier for any fully distributed protocol in sparse networks.

Reading between the lines

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

  • The base case at t1 = Θ(√n) is asserted rather than derived: Lemma 9 says the honest subgraph is an expander there by it is easy to show and by symmetry arguments. If that base case is false, the induction in Lemma 8 has no starting point; this is the place to attack the theorem.
  • The protocol tolerates only stochastic churn; extending the same construction to adversarial churn would require a different argument, since the entry manager and phase-based refresh both rely on Poisson arrival and memoryless departure statistics.
  • A natural testable extension is to instantiate the protocol at moderate n and measure whether the honest subgraph's conductance stays above a fixed constant across phases; the theorem predicts this for all sufficiently large n, and simulation could expose an early-n breakdown or an unexpectedly large constant.
  • The verified-token mechanism suggests a general template: any task that needs uniform sampling in a Byzantine network can be layered on these random walks as long as a core expander exists.
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 / 4 minor

Summary. The paper presents a randomized, fully-distributed protocol (Algorithm 1) that aims to construct and maintain a bounded-degree expander graph among honest nodes in a dynamic peer-to-peer network subject to stochastic churn and a full-information Byzantine adversary. The protocol uses an entry manager, phase-based edge rewirings, and a Byzantine random-walk sampling mechanism adapted from the authors' earlier work. The main result (Theorem 2) claims that for every t >= Θ(√n), with probability 1 - 1/n^Ω(1), the maintained graph contains a constant-degree expander subgraph of size (1 - o(1))|V_t| while tolerating o(|V_t|/log |V_t|) Byzantine nodes. The proof proceeds by induction over phases: Lemma 8 assumes an expander core at the start of a phase and shows the invariant is preserved; Lemma 9 is supposed to establish the base case at t = Θ(√n).

Significance. If the main theorem were proved, the result would be significant: it would provide the first protocol that actually constructs and maintains an expander under both continuous churn and a large Byzantine population, thereby removing the ever-present-expander assumption used in several prior distributed algorithms. The protocol is lightweight and plausible, and the paper explicitly connects the construction to existing Byzantine agreement and leader-election algorithms. The authors also correctly identify the key difficulty of controlling Byzantine influence on random-walk sampling and use a phase-based reconnection mechanism to fight expansion decay. However, the proof as written contains a serious gap in the base case of the induction and an unsupported treatment of edges that survive from previous phases; these issues are load-bearing for the claimed theorem. The paper ships no machine-checked proofs or reproducible code; its main assets are the algorithmic idea and the high-level structure of the proof.

major comments (4)
  1. [Section 3.3, Lemma 9] Lemma 9, which is the base case for the entire induction, is asserted rather than proved. The proof says 'it is easy to show (similar to the argument in Lemma 8) that all subsets of S2 have conductance at least phi'' and 'By symmetry, for d sufficiently large, we can show that all subsets in S1 have conductance at least phi''. No derivation is given for either statement. This is not a minor omission: the induction in Lemma 8 and the Byzantine Random Walk Theorem (Theorem 1) both require that the honest subgraph at the start of each phase is an expander, and Lemma 9 is the only place where the initial expander at t1 = Θ(√n) is supposed to be established. Moreover, the S1 case is not symmetric to the initial-joining analysis: by time t1 the nodes in S1 have already been through Θ(√n/log n) phases in which they dropped and reconnected edges, so the graph induced by S1 is not the simple random graph created when those nodes first joined. The proof therefore either ignores the effect of earlier rewirings or implicitly assumes the very property it must prove.
  2. [Section 3.3, Lemma 8] The induction step treats all outgoing edges in ES as independent, freshly random edges with Pr(X_i = 1) ≤ aq/n. This is not justified by Algorithm 1: in each phase a node drops only d of its connections when its outgoing degree is at least 2d, and otherwise establishes up to 3d - d_out connections; a large fraction of the edges present at time t+η log n are edges that survived from earlier phases. Those surviving edges are correlated with the history of rewirings and are not independent random samples from the current node set. The conductance bound `|ES| - |E(S,S)| >= phi'|ES|` is proved by treating all edges as if they were freshly sampled at the end of the phase. As written, the argument does not apply to the actual graph maintained by the protocol, so the induction step does not establish the invariant.
  3. [Section 3.3, Lemma 8 (equation with |ES|)] The displayed equation `|ES| = |E(S, S)| + |E(S, S)|` is internally inconsistent: both terms on the right are identical, so it would imply |E(S,S)| = 0. The intended second term is presumably |E(S, V \ S)| (or E(S, \bar S)), but as written the equation is meaningless. Since this equation is the starting point for the conductance calculation, it must be corrected and the subsequent bound re-derived before the proof can be evaluated.
  4. [Section 3.3, Lemma 8, treatment of new nodes] The last paragraph of the lemma asserts that new nodes joining during a phase connect to at least d nodes supplied by the Entry Manager, that each such connection has constant probability of connecting to the core, and that 'it is easy to show that any subset of the new nodes has conductance at least phi''. Lemma 6 only analyzes a single new node's success probability in one connection attempt; it does not jointly analyze the set of Θ(log n) new nodes in a phase, accounting for incoming-degree caps, token verification, and the fact that a new node's candidate list is drawn from the entry manager's nodesList rather than from the core. A joint conductance argument for the newly added nodes is needed for the induction step to go through, but none is provided.
minor comments (4)
  1. [Section 3.3, notation in Lemma 8] The notation E(U, V) is used before it is defined, and the definition in the proof ('the set of edges with a node in set U connected by an outgoing edge to a node in set V') is informal and does not resolve the S/S duplication. Please define the cut notation and fix all occurrences consistently.
  2. [Section 2, Algorithm 1 description] The prose around the new-node connection rule says a node accepts a connection 'if the connection is a verified one and if the incoming degree is 6d; otherwise it will reject'. This appears to be the opposite of the intended rule, which should accept when the incoming degree is less than 6d. The pseudocode in Algorithm 1 (lines 9-12) is clearer, but the prose should be corrected to match it.
  3. [Section 3.3, Lemma 8 proof] The proof refers to 'the same theorem for time steps between this phase' and says the core 'proves the theorem for time steps between this phase', but the invariant is only stated for phase boundaries. The intermediate-time argument is sketched in one sentence and should be expanded or made precise.
  4. [Section 3.1, Theorem 1 and Definition 3.2] Theorem 1 is imported as an adaptation of the Byzantine Random Walk Theorem from [5], but the manuscript should state explicitly which parts of the proof are new for the dynamic setting and which are verbatim from [5]. Moreover, Lemma 12 has a sentence beginning 'As lemma the states' and a comparison that is difficult to parse; please rewrite it.

Circularity Check

1 steps flagged · score 3.0 of 10

The main induction is anchored only by an unproved base case: Lemma 9 asserts expansion at t1=Θ(√n) with 'easy to show' and 'by symmetry', effectively assuming the expander core that Theorem 1 and Lemma 8 need.

  1. other [Section 3.3, Lemma 9; used as the base case of Lemma 8 and Theorem 2]
    "Since nodes in S2 connect to nodes in S1 almost uniformly at random, it is easy to show (similar to the argument in Lemma 8) that all subsets of S2 have conductance at least ϕ′ for a suitable constant ϕ′. By symmetry, for d sufficiently large, we can show that all subsets in S1 have conductance at least ϕ′."

    Lemma 8's induction rests on the base case at t1=Θ(√n), and Lemma 9 is the only place where that base is supposed to be established. But by time t1 the protocol has already run Θ(√n/log n) phases of verified-token rewiring, and the Byzantine Random Walk Theorem (Theorem 1) used for those rewirings is itself conditional on an expander core at the start of each phase (Definition 3.2; Lemma 15 says 'Since the graph remains an expander throughout the phase'). Lemma 9 does not analyze the actual rewired subgraph S1; it only uses the Entry Manager's near-uniform choices for new nodes in S2, then asserts conductance for S2 by 'it is easy to show' and for S1 'By symmetry'.

full rationale

The central construction is a legitimate induction if its base case were established: each phase assumes a core expander, uses the Byzantine Random Walk Theorem to obtain near-uniform sampling, and then proves by a Chernoff/union-bound argument that the rewired honest graph is again an expander (Lemma 8). Theorem 1 is imported from the authors' prior SODA paper [5], but the appendix gives a full adaptation proof, so this is not a bare self-citation. Lemmas 4, 5, and 6 are independent entry-manager and concentration arguments. The serious problem is the base case: Lemma 9 does not prove that G_{t1} is an expander after the protocol has already been rewiring edges for Θ(√n/log n) phases; it asserts the needed conductance with 'it is easy to show' and 'by symmetry'. This is a load-bearing bootstrap gap rather than an equation-level reduction: the main theorem is incomplete because the induction is not anchored. I therefore assign a moderate score of 3, reflecting one substantial unproved base-case dependency, not a conclusion forced by construction or by a self-citation chain.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the stochastic churn model, the full-information Byzantine bound, a trusted entry manager, and a bootstrap assumption that an expander already exists at Theta(sqrt(n)). The protocol parameters d, a, c, eta, and phi are chosen constants, not fitted to data. No new physical or computational entities are postulated beyond protocol constructs like verified tokens and the core subgraph.

free parameters (5)
  • d = a constant, stated to be suitably large (e.g., less than 10)
    Bounds outgoing (3d) and incoming (6d) degrees; chosen by hand to make conductance and sampling arguments work.
  • a = large enough fixed constant
    Scales the token cap cap = a log^3 n per edge per round; chosen large enough to ensure tokens are not dropped with high probability.
  • c = large enough constant
    Sets the random walk length rwLength = c log n; must be at least the core mixing time.
  • eta (phase length factor) = large enough constant
    Sets the phase length eta log n; must exceed 2rwLength to allow verified tokens to return.
  • phi (conductance target) = constant in (0, phi')
    Target conductance of the maintained honest subgraph; chosen in the proof, with phi' the base conductance.
assumptions (6)
  • domain assumption Node arrivals form a Poisson process with rate lambda = 1 and lifetimes are exponential with mean n (M/M/Infinity churn model).
    Model adopted from [38]; the paper's theorem depends on the resulting stable size and concentration bounds (Definition 1.2, Lemma 1).
  • domain assumption The Byzantine adversary is full-information, can corrupt nodes only when they join, and the number of Byzantine nodes at any time is o(n/log n).
    Section 1.1 model; the argument that most random walks stay in the honest core depends on this bound.
  • ad hoc to paper The entry manager is reliable and its nodesList is a near-uniform sample of live nodes.
    Lemma 4 attempts to prove near-uniformity, but the entry manager is not modeled as Byzantine; if it were, new nodes could be directed to adversarial nodes and the base case and joining lemma fail.
  • ad hoc to paper At time Theta(sqrt(n)) the honest subgraph is an expander of constant conductance.
    Lemma 9 asserts this with a sketch ('it is easy to show'); it is load-bearing for the induction in Lemma 8.
  • standard math Removing o(n) Byzantine nodes from an expander leaves an expander subgraph (core property).
    Invoked from [9], Section 1.6, to define the core subgraph of honest nodes.
  • domain assumption The Byzantine Random Walk Theorem of [5] extends to the dynamic core subgraph.
    Stated as Theorem 1 and proven in the appendix by adaptation; the proof itself assumes the core is a static expander.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks." pith.science (2026). https://pith.science/paper/A3HWWVOH

@misc{pith2026250604368,
  author       = {Pith},
  title        = {Pith review of: Fully-Distributed Construction of Byzantine-Resilient Dynamic Peer-to-Peer Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A3HWWVOH}},
  note         = {Machine review of arXiv:2506.04368}
}
abstract

We address a fundamental problem in Peer-to-Peer (P2P) networks, namely, constructing and maintaining dynamic P2P overlay network topologies with essential properties such as connectivity, low diameter, and high expansion, that are resilient to continuous high churn and the presence of a large number of malicious (Byzantine) nodes. Our main goal is to construct and maintain a sparse (bounded degree) expander topology despite high churn and a large number of Byzantine nodes. Such an expander topology has logarithmic diameter, high expansion, and is robust to churn and the presence of a large number of bad nodes, and facilitates efficient and robust algorithms for fundamental problems in distributed computing, such as agreement, broadcasting, routing, etc. Our main contribution is a randomized, fully-distributed dynamic P2P protocol that works with only local initial knowledge and guarantees, with a high probability, the maintenance of a constant degree graph with high expansion even under continuous churn and in the presence of a large number of Byzantine nodes. Our protocol can tolerate up to $o(n/poly\log(n))$ Byzantine nodes (where $n$ is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only $O(poly\log(n))$ overhead for topology maintenance: only polylogarithmic (in $n$) bits need to be processed and sent by each honest node per round, and any honest node's computation cost per round is also polylogarithmic. Our protocol can be used as a building block for solving fundamental distributed computing problems in highly dynamic networks, such as Byzantine agreement and Byzantine leader election, and enables fast and scalable algorithms for these problems.

Figures

Figures reproduced from arXiv: 2506.04368 by the authors.

Figure 1
Figure 1. The figure illustrates how the tokens are being sent in the starting [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. The figure illustrates the core subgraph in phase [ [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Threshold-Driven Streaming Graph: Expansion and Rumor Spreading

    cs.DC 2025-07 conditional novelty 6.0 of 10

    Combining the RAES threshold link-acceptance rule with streaming node churn produces dynamic expanders with bounded degree, and the paper proves O(log n) push/pull rumor spreading on them.

  2. Trust-Aware Topology Learning for Dynamic Decentralized Federated Learning under Adversaries

    cs.DC 2026-08 conditional novelty 5.0 of 10

    DMTT screens both model updates and topology claims with a Beta-trust model, and on two HAR datasets it is the only tested method that beats local-only learning under 10 to 80 percent Byzantine devices.

Reference graph

Works this paper leans on

53 extracted references · 46 canonical work pages · cited by 2 Pith papers

  1. [1]

    Fast construction of overlay networks

    Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin. Fast construction of overlay networks. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’05, page 145–154, New York, NY, USA, 2005. Association for Computing Machinery

    work page 2005

  2. [2]

    Antonopoulos

    Andreas M. Antonopoulos. Mastering Bitcoin: Programming the Open Blockchain. O’Reilly Media, Inc., 2nd edition, 2017

    work page 2017

  3. [3]

    Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition)

    Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). John Wiley Interscience, March 2004

    work page 2004

  4. [4]

    A fully-distributed scalable peer-to-peer protocol for byzantine-resilient distributed hash tables

    John Augustine, Soumyottam Chatterjee, and Gopal Pandurangan. A fully-distributed scalable peer-to-peer protocol for byzantine-resilient distributed hash tables. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures , SPAA ’22, page 87–98. Association for Computing Machinery, 2022

    work page 2022

  5. [5]

    Fully- distributed byzantine agreement in sparse networks

    John Augustine, Fabien Dufoulon, and Gopal Pandurangan. Fully- distributed byzantine agreement in sparse networks. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 , pages 4172–4197. SIAM, 2025. doi: 10.1137/1.9781611978322.142. 31

    work page doi:10.1137/1.9781611978322.142 2025

  6. [6]

    Storage and search in dynamic peer-to-peer networks

    John Augustine, Anisur Rahaman Molla, Ehab Morsy, Gopal Panduran- gan, Peter Robinson, and Eli Upfal. Storage and search in dynamic peer-to-peer networks. In SPAA, pages 53–62, 2013

    work page 2013

  7. [7]

    Fast byzan- tine agreement in dynamic networks

    John Augustine, Gopal Pandurangan, and Peter Robinson. Fast byzan- tine agreement in dynamic networks. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Com- puting, PODC ’13, Montreal, QC, Canada, July 22-24, 2013 , pages 74–83. ACM, 2013. doi:10.1145/2484239.2484275

    arXiv 2013

  8. [8]

    Fast byzan- tine leader election in dynamic networks

    John Augustine, Gopal Pandurangan, and Peter Robinson. Fast byzan- tine leader election in dynamic networks. In International Symposium on Distributed Computing (DISC) , pages 276–291, 2015

    work page 2015

Show all 53 references
  1. [9]

    Enabling robust and efficient distributed computation in dynamic peer-to-peer networks

    John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, and Eli Upfal. Enabling robust and efficient distributed computation in dynamic peer-to-peer networks. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , FOCS ’15, pa...

    2015 doi

  2. [10]

    Towards robust and efficient computation in dynamic peer-to-peer networks

    John Augustine, Gopal Pandurangan, Peter Robinson, and Eli Up- fal. Towards robust and efficient computation in dynamic peer-to-peer networks. In SODA, pages 551–569, 2012

    2012

  3. [11]

    Awerbuch and C

    B. Awerbuch and C. Scheideler. The hyperring: A low-congestion deterministic data structure for distributed environments. In SODA, pages 318–327, 2004

    2004

  4. [12]

    Towards a scalable and robust dht

    Baruch Awerbuch and Christian Scheideler. Towards a scalable and robust dht. Theory Comput. Syst. , 45(2):234–260, 2009

    2009

  5. [13]

    Expansion and flooding in dynamic random net- works with node churn

    Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi. Expansion and flooding in dynamic random net- works with node churn. Random Structures & Algorithms , 63(1):61–101,

  6. [14]

    Ben-Or and N

    M. Ben-Or and N. Linial. Collective coin flipping. In Silvio Micali, editor, Advances in Computing Research 5: Randomness and Computation , volume 5, pages 91–115. JAI Press, 1989. 32

    1989

  7. [15]

    Byzan- tine agreement in the full-information model in O(log n) rounds

    Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. Byzan- tine agreement in the full-information model in O(log n) rounds. In Proceedings of the Thirty-eighth Annual ACM Symposium on The- ory of Computing , STOC ’06, pages 179–186, New York, NY, USA,

  8. [16]

    Byzantine consensus in asynchronous message-passing systems: a survey

    Miguel Correia, Giuliana Santos Veronese, Nuno Ferreira Neves, and Paulo Verissimo. Byzantine consensus in asynchronous message-passing systems: a survey. Int. J. Crit. Comput.-Based Syst. , 2(2):141–161, July 2011

    2011

  9. [17]

    Moses Jr., and Gopal Pandurangan

    Fabien Dufoulon, Michael Moorman, William K. Moses Jr., and Gopal Pandurangan. Time- and Communication-Efficient Overlay Network Construction via Gossip. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Lei...

    2024 doi

  10. [18]

    Fault tolerance in networks of bounded degree

    Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal. Fault tolerance in networks of bounded degree. SIAM J. Comput. , 17(5):975– 988, 1988

    1988

  11. [19]

    Censorship resistant peer-to-peer content addressable networks

    Amos Fiat and Jared Saia. Censorship resistant peer-to-peer content addressable networks. In SODA, pages 94–103, 2002

    2002

  12. [20]

    Dconstructor: Efficient and robust network construction with polylogarithmic overhead

    Seth Gilbert, Gopal Pandurangan, Peter Robinson, and Amitabh Tre- han. Dconstructor: Efficient and robust network construction with polylogarithmic overhead. In Proceedings of the 39th Symposium on Principles of Distributed Computing , PODC ’20, page 438–447, New York, NY, USA...

    2020

  13. [21]

    Fault-tolerant computation in the full information model

    Oded Goldreich, Shafi Goldwasser, and Nathan Linial. Fault-tolerant computation in the full information model. SIAM J. Comput., 27(2):506– 544, 1998. doi:10.1137/S0097539793246689

    1998 doi

  14. [22]

    Time-optimal construction of overlay networks

    Thorsten G¨ otte, Kristian Hinnenthal, Christian Scheideler, and Ju- lian Werthmann. Time-optimal construction of overlay networks. In 33 Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, page 457–468, New York, NY, USA, 2021. Asso- ciation...

    2021

  15. [23]

    Highly dynamic distributed computing with byzantine failures

    Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec. Highly dynamic distributed computing with byzantine failures. In PODC, pages 176–183, 2013

    2013

  16. [24]

    Asymptotically efficient ap- proaches to fault-tolerance in peer-to-peer networks

    Kirsten Hildrum and John Kubiatowicz. Asymptotically efficient ap- proaches to fault-tolerance in peer-to-peer networks. In DISC, volume 2848 of Lecture Notes in Computer Science , pages 321–336. Springer, 2003

    2003

  17. [25]

    Skip+: A self-stabilizing skip graph

    Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo T¨ aubig. Skip+: A self-stabilizing skip graph. J. ACM , 61(6), December 2014. doi:10.1145/2629695

    2014 doi

  18. [26]

    Stochastic analysis of a churn- tolerant structured peer-to-peer scheme

    Tim Jacobs and Gopal Pandurangan. Stochastic analysis of a churn- tolerant structured peer-to-peer scheme. Peer-to-Peer Networking and Applications, 6(1):1–14, 2013. doi:10.1007/s12083-012-0124-z

    2013 doi

  19. [27]

    Frans Kaashoek and David R

    M. Frans Kaashoek and David R. Karger. Koorde: A simple degree- optimal distributed hash table. In M. Frans Kaashoek and Ion Stoica, editors, Peer-to-Peer Systems II, pages 98–107, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg

    2003

  20. [28]

    Towards secure and scalable computation in peer-to-peer networks

    Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Towards secure and scalable computation in peer-to-peer networks. In FOCS, pages 87–98, 2006

    2006

  21. [29]

    Towards worst- case churn resistant peer-to-peer systems

    Fabian Kuhn, Stefan Schmid, and Roger Wattenhofer. Towards worst- case churn resistant peer-to-peer systems. Distributed Computing , 22(4):249–267, 2010

    2010

  22. [30]

    Law and K.-Y

    C. Law and K.-Y. Siu. Distributed construction of random expander networks. In INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies , volume 3, pages 2133 – 2143 vol.3, march-3 april 2003

    2003

  23. [31]

    Analysis of the evolution of peer-to-peer systems

    David Liben-Nowell, Hari Balakrishnan, and David Karger. Analysis of the evolution of peer-to-peer systems. In Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing , PODC ’02, page 233–242, New York, NY, USA, 2002. Association for Computing M...

    2002

  24. [32]

    Distributed Algorithms

    Nancy Lynch. Distributed Algorithms. Morgan Kaufman Publishers, Inc., San Francisco, USA, 1996

    1996

  25. [33]

    Mahlmann and C

    P. Mahlmann and C. Schindelhauer. Peer-to-peer networks based on random transformations of connected regular undirected graphs. In SPAA, pages 155–164, 2005

    2005

  26. [34]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2004

    2004

  27. [35]

    The dynamic and-or quorum system

    Uri Nadav and Moni Naor. The dynamic and-or quorum system. In Pierre Fraigniaud, editor, Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Pro- ceedings, volume 3724 of Lecture Notes in Computer Science , pages 472–486. Spr...

    2005 doi

  28. [36]

    Scalable and dynamic quorum systems

    Moni Naor and Udi Wieder. Scalable and dynamic quorum systems. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, PODC ’03, page 114–122, New York, NY, USA,

  29. [37]

    A simple fault tolerant distributed hash table

    Moni Naor and Udi Wieder. A simple fault tolerant distributed hash table. In IPTPS, pages 88–97, 2003

    2003

  30. [38]

    Building low-diameter p2p networks

    Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal. Building low-diameter p2p networks. In FOCS, pages 492–499, 2001

    2001

  31. [39]

    Dex: Self- healing expanders

    Gopal Pandurangan, Peter Robinson, and Amitabh Trehan. Dex: Self- healing expanders. In Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS) , pages 702–711. IEEE, 2014. doi:10.1109/IPDPS.2014.78

    2014 doi

  32. [40]

    Xheal: localized self-healing using expanders

    Gopal Pandurangan and Amitabh Trehan. Xheal: localized self-healing using expanders. In PODC, pages 301–310, 2011

    2011

  33. [41]

    Pease, Robert E

    Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234, 1980

    1980

  34. [42]

    Distributed Computing: A Locality-Sensitive Approach

    David Peleg. Distributed Computing: A Locality-Sensitive Approach . SIAM Society for Industrial and Applied Mathematics Monographs on Discrete Mathematics ans Applications, Philadelphia, 2000. 35

    2000

  35. [43]

    Karp, and Scott Shenker

    Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard M. Karp, and Scott Shenker. A scalable content-addressable network. In Rene L. Cruz and George Varghese, editors, Proceedings of the ACM SIGCOMM 2001 Conference on Applications, Technologies, Architectures, and Protocols fo...

    2001

  36. [44]

    Rowstron and P

    A. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proc. of the IFIP/ACM Intenrational Conference on Distributed Systems Platforms , pages 329–350, 2001

    2001

  37. [45]

    How to spread adversarial nodes?: rotate! In Harold N

    Christian Scheideler. How to spread adversarial nodes?: rotate! In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005 , pages 704–713. ACM, 2005. doi:10.1145/ 1060590.1060694

    2005

  38. [46]

    A distributed and oblivious heap

    Christian Scheideler and Stefan Schmid. A distributed and oblivious heap. In Automata, Languages and Programming, volume 5556 of Lecture Notes in Computer Science , pages 571–582. Springer Berlin / Heidelberg, 2009

    2009

  39. [47]

    Stoica, R

    I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In the Proceedings of the 2001 ACM SIGCOMM Conference , pages 149–160, 2001

    2001

  40. [48]

    Understanding churn in peer-to-peer networks

    Daniel Stutzbach and Reza Rejaie. Understanding churn in peer-to-peer networks. In Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, IMC ’06, pages 189–202, New York, NY, USA,

  41. [49]

    Blockchain Science: Distributed Ledger Technology

    Roger Wattenhofer. Blockchain Science: Distributed Ledger Technology . CreateSpace Independent Publishing Platform, North Charleston, SC, USA, 3rd edition, 2019

    2019

  42. [50]

    B. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, UC Berkeley , April, 2001. 36 5 Appendix 5.1 Proof of Lemma 2 Proof. In a Poisson process with rate λ = 1, the number of nod...

    2001

  43. [2003]

    doi:10.1145/872035

    Association for Computing Machinery. doi:10.1145/872035. 872052

    doi

  44. [2006]

    URL: http://doi.acm.org/10.1145/1132516.1132543, doi:10.1145/1132516.1132543

    ACM. URL: http://doi.acm.org/10.1145/1132516.1132543, doi:10.1145/1132516.1132543

  45. [2023]

    1002/rsa.21133, doi:10.1002/rsa.21133

    URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/ rsa.21133, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10. 1002/rsa.21133, doi:10.1002/rsa.21133

    doi

Pith tools

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