Toward more localized local algorithms: removing assumptions concerning global knowledge

DOI10.1007/S00446-012-0174-8MaRDI QIDQ2441787zbMATH OpenOpenAlexFDO

Authors Amos Korman, Jean-Sébastien Sereni, Laurent Viennot

Publication date 28 March 2014

Published in Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

parametersdistributed algorithmcoloringmaximal matchingMISglobal knowledge

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Distributed algorithms (68W15)

Abstract: Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and $(Delta+1)$-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [34], as well as the $O(Delta2)$-coloring algorithm by Linial [28]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, local algorithms generally use good estimations of one or more global parameters of the network, e.g., the maximum degree $Delta$ or the number of nodes n. This paper provides a method for transforming a non-uniform local algorithm into a uniform one. Furthermore , the resulting algorithm enjoys the same asymp-totic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all state of the art non-uniform algorithms for MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.

Recommendations

• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• An Improved Distributed Algorithm for Maximal Independent Set
• The locality of distributed symmetry breaking
• Deterministic stateless centralized local algorithms for bounded degree graphs

Cites work

• 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 technique for distributed symmetry breaking
• An almost optimal algorithm for unbounded searching
• An optimal maximal independent set algorithm for bounded-independence graphs
• Automata, Languages and Programming
• Communication algorithms with advice
• Complexity of network synchronization
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed Computing: A Locality-Sensitive Approach
• Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
• Distributed approximate matching
• Distributed computing with advice: information sensitivity of graph coloring
• Distributed deterministic edge coloring using bounded neighborhood independence
• Distributed verification of minimum spanning trees
• Drawing maps with advice
• Label-guided graph exploration by a finite automaton
• Local Distributed Decision
• Local MST computation with short advice
• Locality based graph coloring
• Locality in Distributed Graph Algorithms
• On the Complexity of Distributed Network Decomposition
• On the complexity of distributed graph coloring
• On the distributed complexity of computing maximal matchings
• On the locality of distributed sparse spanner construction
• Parallel Symmetry-Breaking in Sparse Graphs
• Proof labeling schemes
• Some simple distributed algorithms for sparse networks
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Tight Fault Locality
• What Can be Computed Locally?
• What cannot be computed locally!

Cited in

(10)

• Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
• Improved deterministic distributed matching via rounding
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Fast rendezvous on a cycle by agents with different speeds
• Adapting local sequential algorithms to the distributed setting
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• A time hierarchy theorem for the LOCAL model
• The ANTS problem
• An exponential separation between randomized and deterministic complexity in the LOCAL model

This page was built for publication: Toward more localized local algorithms: removing assumptions concerning global knowledge

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