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.
翻译:分布式图表算法基本上是一种算法, 每一个图表的节点都可以在图形中的某个距离查看其周围, 并选择其输出。 由于分布式环境存在错误, 一个重要的问题是能够检查输出是否正确, 或者一般地说, 网络对于某些上游的配置是否正确。 人们希望这个检查非常本地化, 以避免使用过多的资源。 不幸的是, 大多数的上游无法通过这个方式检查, 也就是验证起作用的地方 。 本地认证( 也称为 校对标签计划、 本地可核对的证明或分布式验证) 包括给节点分配标签, 以证明配置正确 。 在这个问题上有好几种观点: 它可以被看作是自我稳定算法的一部分, 标记问题, 或者非定义性分布式的决定 。 本文是本地认证域的介绍, 概括了历史、 技术和当前研究方向 。