Derandomizing local distributed algorithms under bandwidth restrictions

DOI10.1007/s00446-020-00376-1zbMath1445.68333arXiv1608.01689OpenAlexW3017383812MaRDI 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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Network Decomposition and Distributed Derandomization (Invited Paper), Deterministic Massively Parallel Connectivity, Superfast coloring in CONGEST via efficient color sampling, Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set, Congested Clique Algorithms for Graph Spanners, Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC, 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