Derandomizing local distributed algorithms under bandwidth restrictions

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

Mathematics Subject Classification ID

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