Renaming in distributed certification
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909929233711104 |
|---|---|
| author | Bousquet, Nicolas Esperet, Louis Feuilloley, Laurent Zeitoun, Sébastien |
| author_facet | Bousquet, Nicolas Esperet, Louis Feuilloley, Laurent Zeitoun, Sébastien |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15404 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Renaming in distributed certification Bousquet, Nicolas Esperet, Louis Feuilloley, Laurent Zeitoun, Sébastien Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms 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. |
| title | Renaming in distributed certification |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.15404 |