Introduction to local certification
From MaRDI portal
Publication:5024672
Abstract: A distributed graph algorithm is basically an algorithm where every node of a graph can look at its neighborhood at some distance in the graph and chose its output. As distributed environment are subject to faults, an important issue is to be able to check that the output is correct, or in general that the network is in proper configuration with respect to some predicate. One would like this checking to be very local, to avoid using too much resources. Unfortunately most predicates cannot be checked this way, and that is where certification comes into play. Local certification (also known as proof-labeling schemes, locally checkable proofs or distributed verification) consists in assigning labels to the nodes, that certify that the configuration is correct. There are several point of view on this topic: it can be seen as a part of self-stabilizing algorithms, as labeling problem, or as a non-deterministic distributed decision. This paper is an introduction to the domain of local certification, giving an overview of the history, the techniques and the current research directions.
Recommendations
Cites work
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A hierarchy of local decision
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Approximate proof-labeling schemes
- Asynchronous distributed automata: a characterization of the modal \(\mu\)-fragment
- Communication Complexity
- Compact Distributed Certification of Planar Graphs
- Compact distributed certification of planar graphs
- Computational Complexity
- Deterministic coin tossing with applications to optimal parallel list ranking
- Distributed computing with advice: information sensitivity of graph coloring
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed verification of minimum spanning trees
- Distributedly testing cycle-freeness
- Error-sensitive proof-labeling schemes
- scientific article; zbMATH DE number 7765409 (Why is no real title available?)
- Interactive distributed proofs
- Local verification of global proofs
- Locality in Distributed Graph Algorithms
- Locally checkable proofs in distributed computing
- Memory requirements for silent stabilization
- On the Impact of Identifiers on Local Decision
- Oracle size, a new measure of difficulty for communication tasks
- Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
- Parallel \((\Delta +1)\)-coloring of constant-degree graphs
- Proof labeling schemes
- Proof labeling schemes
- Proof-labeling schemes: broadcast, unicast and in between
- Randomized proof-labeling schemes
- Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
- Self-stabilization
- Silent MST Approximation for Tiny Memory
- Survey of distributed decision
- The local detection paradigm and its applications to self-stabilization
- The power of distributed verifiers in interactive proofs
- Towards a complexity theory for local distributed computing
- Trade-offs in distributed interactive proofs
- Tree exploration with advice
- What Can be Computed Locally?
- What can be decided locally without identifiers?
- What can be verified locally?
Cited in
(22)- Compact distributed certification of planar graphs
- Local certification of graphs on surfaces
- Planarity can be verified by an approximate proof labeling scheme in constant-time
- A hierarchy of local decision
- Labeling schemes for deterministic radio multi-broadcast
- Survey of distributed decision
- On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
- Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width
- What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
- On certifying distributed algorithms: problem of local correctness
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- Locally verifiable distributed SNARGs
- Distributed model checking on graphs of bounded treedepth
- Renaming in distributed certification
- Local certification of local properties: tight bounds, trade-offs and new parameters
- Decreasing verification radius in local certification
- Local certification of local properties: tight bounds, trade-offs, and new parameters
- Brief announcement: Global certification via perfect hashing
- A LOCAL view of the polynomial hierarchy
- A subquadratic certification scheme for P₅-free graphs
- Local certification of geometric graph classes
- Reductions in local certification
This page was built for publication: Introduction to local certification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5024672)
