Derandomizing local distributed algorithms under bandwidth restrictions

DOI10.1007/S00446-020-00376-1zbMATH Open1445.68333arXiv1608.01689OpenAlexW3017383812MaRDI QIDQ2189176FDOQ2189176

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

Publication date: 15 June 2020

Published in: Distributed Computing (Search for Journal in Brave)

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}^{*}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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)