Overlay network construction: improved overall and node-wise message complexity

DOI10.4230/LIPICS.FSTTCS.2025.21MaRDI QIDQ7391893zbMATH OpenFDO

Authors Yi-Jun Chang, Yan-Yu Chen, Gopinath Mishra

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2025.21

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• \(\mathrm{SKIP}^{+}\), a self-stabilizing skip graph
• An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
• Building low-diameter P2P networks
• Building self-stabilizing overlay networks with the transitive closure framework
• Computing Shortest Paths and Diameter in the Hybrid Network Model
• Construction and impromptu repair of an MST in a distributed network with o(m) communication
• DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed monitoring of network properties: the power of hybrid networks
• Enabling robust and efficient distributed computation in dynamic peer-to-peer networks
• Expander graphs and their applications
• Fast Byzantine agreement in dynamic networks
• Fast Byzantine leader election in dynamic networks
• Faster construction of overlay networks
• scientific article; zbMATH DE number 2079362 (Why is no real title available?)
• scientific article; zbMATH DE number 2080852 (Why is no real title available?)
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• scientific article; zbMATH DE number 7788449 (Why is no real title available?)
• scientific article; zbMATH DE number 7788464 (Why is no real title available?)
• Optimal lower bounds for distributed and streaming spanning forest computation
• Perigee: Efficient Peer-to-Peer Network Design for Blockchains
• Probability and Computing
• Sampling regular graphs and a peer-to-peer network
• Shortest Paths in a Hybrid Network Model
• Time- and communication-efficient overlay network construction via gossip
• Time-optimal construction of overlay networks
• Towards robust and efficient computation in dynamic peer-to-peer networks
• Universally optimal information dissemination and shortest paths in the HYBRID distributed model

This page was built for publication: Overlay network construction: improved overall and node-wise message complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7391893)