Derandomizing local distributed algorithms under bandwidth restrictions

DOI10.1007/S00446-020-00376-1MaRDI QIDQ2189176zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, M. Parter, Gregory Schwartzman

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, https://drops.dagstuhl.de/opus/volltexte/2017/7975/

Mathematics Subject Classification ID

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

Abstract: This paper addresses the cornerstone family of emph{local problems} in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the $n$ nodes can only send $O(logn)$-bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in $O(Dlo{g}^{2}n)$ rounds, where $D$ is the diameter of the graph. The best known running time in terms of $n$ alone is $2^{O(sqrtlogn)}$, which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based $O(Delta+lo{g}^{\ast }n)$-round algorithm, where $Delta$ is the maximal degree in the graph. On the way to obtaining the above, we show that in the emph{Congested Clique} model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in $O(logDeltalogn)$ rounds.%, where $Delta$ is the maximum degree. When $Delta=O(n^{1/3})$, the bound improves to $O(logDelta)$ and holds also for $(Delta+1)$-coloring. In addition, we deterministically construct a $(2k-1)$-spanner with $O(k{n}^{1+1/k}logn)$ edges in $O(klogn)$ rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a $(2k-1)$-spanner with $O(k{n}^{1+1/k})$ edges runs in $O(n^{1-1/k})$ rounds.

Recommendations

• Derandomizing local distributed algorithms under bandwidth restrictions
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• On the complexity of local distributed graph problems
• Distributed MIS via all-to-all communication
• An Improved Distributed Algorithm for Maximal Independent Set

Cites work

• scientific article; zbMATH DE number 18532 (Why is no real title available?)
• scientific article; zbMATH DE number 1833421 (Why is no real title available?)
• A Fast Derandomization Scheme and Its Applications
• A New Parallel Algorithm for the Maximal Independent Set Problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A fast and simple randomized parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• A lower bound for the distributed Lovász local lemma
• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• An Improved Distributed Algorithm for Maximal Independent Set
• Approximation of distances and shortest paths in the broadcast congest clique
• Automata, Languages and Programming
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
• Deterministic algorithms for the Lovász local lemma
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed MIS via all-to-all communication
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Distributed approximation algorithms for weighted shortest paths
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
• Lessons from the Congested Clique Applied to MapReduce
• Local Computation of Nearly Additive Spanners
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• MST in \(O(1)\) rounds of congested clique
• MST in log-star rounds of congested clique
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• On the locality of distributed sparse spanner construction
• On the power of the congested clique model
• Optimal deterministic routing and sorting on the congested clique
• Pseudorandomness
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Removing randomness in parallel computation without a processor penalty
• Simulating (log ^c n )-wise independence in NC
• Sublinear fully distributed partition with applications
• Survey of local algorithms
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• The locality of distributed symmetry breaking
• The probabilistic method yields deterministic parallel algorithms
• The round complexity of distributed sorting, extended abstract
• Tight bounds for parallel randomized load balancing
• Toward optimal bounds in the congested clique, graph connectivity and MST
• What Can be Computed Locally?
• \((\Delta+1)\) coloring in the congested clique model
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)

Cited in

(11)

• Near-optimal scheduling in the congested clique
• Faster deterministic distributed MIS and approximate matching
• Derandomizing local distributed algorithms under bandwidth restrictions
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Bounds for the optimal decentralized access protocol in a local area network
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Congested clique algorithms for graph spanners
• Fooling views: a new lower bound technique for distributed computations under congestion
• Coloring fast without learning your neighbors' colors
• Superfast coloring in CONGEST via efficient color sampling
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC

This page was built for publication: Derandomizing local distributed algorithms under bandwidth restrictions

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