Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Introduction to loca ...
Article

Introduction to local certification

Laurent Feuilloley
Download article
Open on arXiv
Submitted on
April 14, 2020
Accepted on
September 5, 2021
Published on
September 15, 2021
Last modified on
March 31, 2025
Volume 23
vol. 23:3
Distributed Computing and Networking
DOI
10.46298/dmtcs.6280
License
arXiv.org - Non-exclusive license to distribute
Indicators
1861
Views
1337
Downloads

Introduction to local certification

Laurent Feuilloley
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. Comment: Final version for DMTCS
Keywords
  • Computer Science - Distributed, Parallel, and Cluster Computing
  • Computer Science - Data Structures and Algorithms
Mathematics Subject Classification 2020
  • 05C78 - Graph labelling (graceful graphs, bandwidth, etc.)
  • 05C82 - Small world graphs, complex networks (graph-theoretic aspects)
  • 05C85 - Graph algorithms (graph-theoretic aspects)
  • 68M14 - Distributed systems
  • 68R10 - Graph theory (including graph drawing) in computer science
Cited by

Source: OpenCitations

  • A subquadratic certification scheme for P5-free graphs

    Theoretical Computer Science

    Authors : Nicolas Bousquet, Sébastien Zeitoun ORCID

    Journal reference : Volume 1033, 2025, pp. 115091

    DOI : 10.1016/j.tcs.2025.115091

  • Optimal Local Certification on Graphs of Bounded Pathwidth

    Proceedings of the ACM Symposium on Principles of Distributed Computing

    Authors : Dan Alden Baterisna, Yi-Jun Chang ORCID

    Journal reference : Volume , 2025, pp. 99-109

    DOI : 10.1145/3732772.3733503

  • Decreasing Verification Radius in Local Certification

    arXiv (Cornell University)

    Authors : Laurent Feuilloley ORCID, Jan Janoušek ORCID, Jan Matyáš Křišťan ORCID, Josef Erik Sedláček ORCID

    Journal reference : Volume , 2024, pp. 188-201

    DOI : 10.1007/978-3-031-74580-5_14

  • Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters

    arXiv (Cornell University)

    Authors : Bousquet, Feuilloley, Zeitoun

    Journal reference : Volume , 2023, pp.

    DOI : 10.4230/lipics.stacs.2024.21

  • Brief Announcement: Global certification via perfect hashing

    Authors : Nicolas Bousquet ORCID, Laurent Feuilloley ORCID, Sébastien Zeitoun ORCID

    Journal reference : Volume , 2024, pp. 429-431

    DOI : 10.1145/3662158.3662781

  • Complexity Landscape for Local Certification

    arXiv (Cornell University)

    Authors : Bousquet, Feuilloley, Zeitoun

    Journal reference : Volume , 2025, pp.

    DOI : 10.4230/lipics.disc.2025.18

  • Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width

    Journal of Graph Theory

    Authors : Oliver Bachtler ORCID, Irene Heinrich ORCID

    Journal reference : Volume 104, 2023, pp. 289-319

    DOI : 10.1002/jgt.22964

  • A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs

    arXiv (Cornell University)

    Authors : Linda Cook ORCID, Eun Jung Kim ORCID, Tomáš Masařík ORCID

    Journal reference : Volume , 2025, pp. 110-120

    DOI : 10.1145/3732772.3733562

  • Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms

    Discrete Mathematics & Theoretical Computer Science

    Authors : Lélia Blin ORCID, Laurent Feuilloley ORCID, Gabriel Le Bouder

    Journal reference : Volume vol. 25:1, 2023, pp.

    DOI : 10.46298/dmtcs.9335

  • Local certification of graph decompositions and applications to minor-free classes

    Journal of Parallel and Distributed Computing

    Authors : Nicolas Bousquet ORCID, Laurent Feuilloley ORCID, Théo Pierron ORCID

    Journal reference : Volume 193, 2024, pp. 104954

    DOI : 10.1016/j.jpdc.2024.104954

  • Local Certification of Local Properties: Tight Bounds, Trade-Offs, and New Parameters

    SIAM Journal on Discrete Mathematics

    Authors : Nicolas Bousquet ORCID, Laurent Feuilloley ORCID, Sébastien Zeitoun ORCID

    Journal reference : Volume 39, 2025, pp. 1974-2002

    DOI : 10.1137/24m1650041

  • Reductions in Local Certification

    Lecture notes in computer science

    Authors : Louis Esperet ORCID, Sébastien Zeitoun ORCID

    Journal reference : Volume , 2026, pp. 192-204

    DOI : 10.1007/978-3-032-11835-6_14

  • Renaming in distributed certification

    arXiv (Cornell University)

    Authors : Nicolas Bousquet, Louis Esperet ORCID, Laurent Feuilloley ORCID, Sébastien Zeitoun ORCID

    Journal reference : Volume 1061, 2025, pp. 115643

    DOI : 10.1016/j.tcs.2025.115643

  • A Survey: SWAP Test and Its Applications to Quantum Complexity Theory

    Algorithmic Foundations for Social Advancement

    Authors : Harumichi Nishimura ORCID

    Journal reference : Volume , 2025, pp. 243-261

    DOI : 10.1007/978-981-96-0668-9_16

  • Local Certification of Graph Decompositions and Applications to Minor-Free Classes

    SSRN Electronic Journal

    Authors : Nicolas Bousquet ORCID, Laurent Feuilloley ORCID, Théo Pierron ORCID

    Journal reference : Volume , 2022, pp.

    DOI : 10.2139/ssrn.4223289

  • Error-sensitive proof-labeling schemes

    Journal of Parallel and Distributed Computing

    Authors : Laurent Feuilloley ORCID, Pierre Fraigniaud

    Journal reference : Volume 166, 2022, pp. 149-165

    DOI : 10.1016/j.jpdc.2022.04.015

  • A LOCAL View of the Polynomial Hierarchy

    Authors : Fabian Reiter ORCID

    Journal reference : Volume , 2024, pp. 347-357

    DOI : 10.1145/3662158.3662774

  • Locally Verifiable Distributed SNARGs

    Lecture notes in computer science

    Authors : Eden Aldema Tshuva, Elette Boyle ORCID, Ran Cohen ORCID, Tal Moran ORCID, Rotem Oshman ORCID

    Journal reference : Volume , 2023, pp. 65-90

    DOI : 10.1007/978-3-031-48615-9_3

  • Lower Bound for Constant-Size Local Certification

    Lecture notes in computer science

    Authors : Virgina Ardévol Martínez, Marco Caoduro ORCID, Laurent Feuilloley ORCID, Jonathan Narboni ORCID, Pegah Pournajafi, Jean-Florent Raymond ORCID

    Journal reference : Volume , 2022, pp. 239-253

    DOI : 10.1007/978-3-031-21017-4_16

  • Program Correctness through Self-Certification

    Communications of the ACM

    Authors : Kedar S. Namjoshi ORCID, Lenore D. Zuck ORCID

    Journal reference : Volume 68, 2025, pp. 74-84

    DOI : 10.1145/3689624
Preview
Loading PDF preview...