Introduction to local certification

A distributed graph algorithm is an algorithm where every node determines its output by inspecting its local neighborhood. As distributed environments 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 time. 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. In this paper, we present several different perspectives for studying local certification: as a part of self-stabilizing algorithms, as a 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.