Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are limited to a local verification? In this area, it is often essential to have identifiers, that is, unique integers assigned to the nodes. In this short paper, we show how to reduce the range of the identifiers, in three different settings. More precisely, we show how to rename identifiers in the classical local certification setting, when we can (resp.\ cannot) choose the new identifiers, and we show how a global certificate can help to encode very compactly a new identifier assignment that is not injective in general, but still useful in applications. We conclude with a number of applications of these results: For every $\ell$, there are local certification schemes for the properties of having clique number at most $\ell$, having diameter at most $\ell$, and having independence number at most~2, with certificates of size $O(n)$. We also show that there is a global certification scheme for bipartiteness with a certificate of size $O(n)$. All these results are optimal.

翻译：本地认证是分布式网络计算领域中的一个核心问题：当节点仅能进行本地验证时，如何向网络中的节点证明某个全局属性成立？在该领域中，标识符（即分配给节点的唯一整数）通常是必不可少的。本文通过三个不同场景展示了如何缩减标识符的取值范围。具体而言，我们阐述了在经典本地认证框架下如何实现标识符重命名（包括可自主选择新标识符与不可选择两种情况），并论证了全局证书如何帮助高效编码一种非单射但实际应用有效的新标识符分配方案。最后，我们列举了这些结论的若干应用：对于任意 $\ell$，存在针对以下属性的本地认证方案：最大团规模不超过 $\ell$、直径不超过 $\ell$、以及独立数不超过 2，其证书规模均为 $O(n)$。同时，我们证明了二分图存在证书规模为 $O(n)$ 的全局认证方案。所有这些结果均达到最优界。