EUVIMEDEUVIMED entdecken
Crossref

Introduction to local certification

Laurent Feuilloley

Discrete Mathematics & Theoretical Computer Science · 15.09.2021 · vol. 23, no. 3 (Distributed Computing and...)

DOI: 10.46298/dmtcs.6280 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 15.09.2021. Verfasst von Laurent Feuilloley. Die Arbeit wurde bisher 16-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Feuilloley, L. (2021). Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, vol. 23, no. 3(Distributed Computing and...). https://doi.org/10.46298/dmtcs.6280

Vancouver

Feuilloley L. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science. 2021;vol. 23, no. 3(Distributed Computing and...). doi:10.46298/dmtcs.6280

BibTeX
@article{Feuilloley2021,
  author = {Feuilloley, Laurent},
  title = {Introduction to local certification},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2021},
  volume = {vol. 23, no. 3},
  number = {Distributed Computing and...},
  doi = {10.46298/dmtcs.6280}
}
Kostenlos starten →