Derandomizing local distributed algorithms under bandwidth restrictions
From MaRDI portal
Publication:2189176
DOI10.1007/s00446-020-00376-1zbMath1445.68333arXiv1608.01689MaRDI QIDQ2189176
Gregory Schwartzman, Merav Parter, Keren Censor-Hillel
Publication date: 15 June 2020
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1608.01689
68R10: Graph theory (including graph drawing) in computer science
68W20: Randomized algorithms
68W15: Distributed algorithms
Related Items
Network Decomposition and Distributed Derandomization (Invited Paper), Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set, Congested Clique Algorithms for Graph Spanners, Superfast coloring in CONGEST via efficient color sampling, Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC, Deterministic Massively Parallel Connectivity, Near-optimal scheduling in the congested clique
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A fast and simple randomized parallel algorithm for maximal matching
- Removing randomness in parallel computation without a processor penalty
- The probabilistic method yields deterministic parallel algorithms
- Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
- Sublinear fully distributed partition with applications
- Algebraic methods in the congested clique
- Toward Optimal Bounds in the Congested Clique
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks
- Pseudorandomness
- Survey of local algorithms
- On the locality of distributed sparse spanner construction
- The round complexity of distributed sorting
- On the power of the congested clique model
- Local Computation
- The Locality of Distributed Symmetry Breaking
- A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Fast Deterministic Distributed Algorithms for Sparse Spanners
- Local Computation of Nearly Additive Spanners
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A New Parallel Algorithm for the Maximal Independent Set Problem
- Locality in Distributed Graph Algorithms
- Simulating (log c n )-wise independence in NC
- An Improved Distributed Algorithm for Maximal Independent Set
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- What Can be Computed Locally?
- A Fast Derandomization Scheme and Its Applications
- “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
- Distributed Graph Coloring: Fundamentals and Recent Developments
- (Delta+1) Coloring in the Congested Clique Model
- Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
- The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
- Optimal deterministic routing and sorting on the congested clique
- Distributed approximation algorithms for weighted shortest paths
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A lower bound for the distributed Lovász local lemma
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- MST in Log-Star Rounds of Congested Clique
- Brief Announcement
- Distributed MIS via All-to-All Communication
- A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
- Deterministic Algorithms for the Lovász Local Lemma
- Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
- Tight bounds for parallel randomized load balancing
- Lessons from the Congested Clique Applied to MapReduce
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Automata, Languages and Programming
- Distributed algorithms for ultrasparse spanners and linear size skeletons