Deterministic fault-tolerant connectivity labeling scheme

Izumi, Taisuke; Emek, Yuval; Wadayama, Tadashi et al.

Distributed Computing, 2024, 38(1), 31-50

Number of Access:359（2025-08-16 00:38 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/98811

Link to primary information 

File Format Terms of use Size Views Date.Available Description information
DistribComput_s00446-024-00472-6 pdf None 585 KB 52 2024.12.19  
Creative Commons : Attribution

Item Information

Output File Export EndNote Basic Export Mendeley

Title
Deterministic fault-tolerant connectivity labeling scheme
Creator
NRID
1000020432461 1000020432461
researchmap permalink
taisukeizumi taisukeizumi
Scopus Author ID
8966483500 8966483500
CreatorName
Izumi, Taisuke
CreatorName
Emek, Yuval
NRID
1000020275374 1000020275374
CreatorName
Wadayama, Tadashi
NRID
1000050199692 1000050199692
ORCID
0000-0003-4628-6393 0000-0003-4628-6393
researchmap permalink
read0013797 read0013797
Scopus Author ID
7202640559 7202640559
CreatorName
Masuzawa, Toshimitsu
Subject
Derandomization
Fault-tolerance
Graph sketch
Labeling scheme
Description
The version of record of this article, first published in Distributed Computing, is available online at Publisher’s website: https://doi.org/10.1007/s00446-024-00472-6.
Abstract
The f-fault-tolerant connectivity labeling (f-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices s and t under the presence of at most f faulty edges only from the labels of s, t, and the faulty edges. This paper presents a new deterministic f-FTC labeling scheme attaining O(f²polylog(n))-bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter (in: Proceedings of the 2021 ACM symposium on principles of distributed computing (PODC), pp 445–455, 2021). The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn et al. (in: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems (PODS), pp 5–14, 2012), via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory–Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal ϵ-net theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.
Publisher
Springer Science and Business Media Deutschland GmbH
Source Title
Distributed Computing
Volume (Issue)
38(1)
Page
31-50
Date of Issued
2024-11-04
Language
English
Handle URL
https://hdl.handle.net/11094/98811
PISSN
01782770
eISSN
14320452
Relation.isIdenticalTo
DOI (Publisher Version)
https://doi.org/10.1007/s00446-024-00472-6
Access Rights
open access
CopyRight
This article is licensed under a Creative Commons Attribution 4.0 International License.
oaire:version
Version of Record
Category
学術雑誌論文 Journal Article