Time-optimal construction of overlay networks

DOI10.1007/s00446-023-00442-4arXiv2009.03987MaRDI QIDQ6096036

Christian Scheideler, Kristian Hinnenthal, Julian Werthmann, Thorsten Götte

Publication date: 11 September 2023

Published in: Distributed Computing, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.03987

zbMATH Keywords

randomized algorithmexpanderdistributed protocolpeer-to-peer network

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (2)

Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ The complexity of growing a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Building self-stabilizing overlay networks with the transitive closure framework
• Fast distributed PageRank computation
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
• Faster construction of overlay networks
• Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests
• The Locality of Distributed Symmetry Breaking
• An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)
• An Efficient Parallel Biconnectivity Algorithm
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• An Improved Distributed Algorithm for Maximal Independent Set
• Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
• A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
• Distributed Monitoring of Network Properties: The Power of Hybrid Networks
• Walking randomly, massively, and efficiently
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
• Massively Parallel Computation of Matching and MIS in Sparse Graphs
• Shortest Paths in a Hybrid Network Model
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Distributed Maximal Independent Set using Small Messages
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Minimum cuts in near-linear time
• What cannot be computed locally!
• SKIP ⁺
• Computing Shortest Paths and Diameter in the Hybrid Network Model
• DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead
• Fast distributed algorithms for testing graph properties

This page was built for publication: Time-optimal construction of overlay networks