Local computation: lower and upper bounds

DOI10.1145/2742012zbMATH Open1426.68092arXiv1011.5470OpenAlexW1957963525MaRDI QIDQ3177774FDOQ3177774

Authors: Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer 

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: The question of what can be computed, and how efficiently, are at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a emph{distributed} fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first poly-logarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks.

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

Recommendations

• What cannot be computed locally!
• What Can be Computed Locally?
• Towards a complexity theory for local distributed computing
• On the complexity of local distributed graph problems
• A simple local 3-approximation algorithm for vertex cover

zbMATH Keywords

lower boundsdistributed algorithmsdominating setmaximal independent setvertex coverlocalityapproximation hardnessmaximal matchingbutterfly effectpolylog-local

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Cited In (65)

• Exact distributed sampling
• Distributed dominating sets in interval graphs
• Distributed domination on sparse graph classes
• The energy complexity of diameter and minimum cut computation in bounded-genus networks
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• Distributed MIS in O(log log n) Awake Complexity
• Distributed MIS with Low Energy and Time Complexities
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Near-optimal distributed dominating set in bounded arboricity graphs
• Distributed maximum matching verification in CONGEST
• Local conflict coloring revisited: Linial for lists
• Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
• Fast Distributed Approximation for Max-Cut
• A topological perspective on distributed network algorithms
• Linial for lists
• Distributed independent sets in interval and segment intersection graphs
• Combinatorial algorithms for distributed graph coloring
• Local Computation Schemes with Partially Ordered Preferences
• Distributed distance-\(r\) covering problems on sparse high-girth graphs
• Dynamic networks of finite state machines
• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Local MST computation with short advice
• Logical locality entails frugal distributed computation over graphs (extended abstract)
• Derandomizing local distributed algorithms under bandwidth restrictions
• Distributed set cover approximation: Primal-dual with optimal locality
• Constant space and non-constant time in distributed computing
• (Delta+1) Coloring in the Congested Clique Model
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• What cannot be computed locally!
• Constant-Time Local Computation Algorithms
• Distributed algorithms for the Lovász local lemma and graph coloring
• What Can be Computed Locally?
• On the locality of bounded growth
• Distributed distance domination in graphs with no \(K_{2,t}\)-minor
• Leveraging Linial’s Locality Limit
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• Distributed Approximate Maximum Matching in the CONGEST Model.
• Simple and local independent set approximation
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• Distributed distance-\(r\) covering problems on sparse high-girth graphs
• Distributed Dominating Set Approximations beyond Planar Graphs
• An interpretation of Shenoy and Shafer's axioms for local computation
• Can we locally compute sparse connected subgraphs?
• Distributed Lower Bounds for Ruling Sets
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• Distributed minimum dominating set approximations in restricted families of graphs
• Veracity radius, capturing the locality of distributed computations
• Distributed reconfiguration of maximal independent sets
• Optimal distributed covering algorithms
• Title not available (Why is that?)
• Input locality and hardness amplification
• What can be sampled locally?
• A time hierarchy theorem for the LOCAL model
• Node and edge averaged complexities of local graph problems
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• Distributed coloring algorithms for triangle-free graphs
• Survey of local algorithms
• Computing large independent sets in a single round
• Distributed Spanner Approximation
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed Reconfiguration of Maximal Independent Sets
• Local planar domination revisited
• Constant round distributed domination on graph classes with bounded expansion

This page was built for publication: Local computation: lower and upper bounds

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