Deterministic fault-tolerant connectivity labeling scheme

Izumi, Taisuke; Emek, Yuval; Wadayama, Tadashi; Masuzawa, Toshimitsu

doi:https://doi.org/10.1007/s00446-024-00472-6

Deterministic fault-tolerant connectivity labeling scheme

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

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

アクセス数:361件（2025-09-01 17:05 集計）

固定URL: https://hdl.handle.net/11094/98811

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
DistribComput_s00446-024-00472-6	pdf	なし	585 KB	52	2024.12.19

Creative Commons : 表示

論文情報

ファイル出力 EndNote Basic出力 Mendeley出力

タイトル	Deterministic fault-tolerant connectivity labeling scheme
著者	NRID 1000020432461 1000020432461 researchmap permalink taisukeizumi taisukeizumi Scopus Author ID 8966483500 8966483500 著者名 Izumi, Taisuke
	著者名 Emek, Yuval
	NRID 1000020275374 1000020275374 著者名 Wadayama, Tadashi
	NRID 1000050199692 1000050199692 ORCID 0000-0003-4628-6393 0000-0003-4628-6393 researchmap permalink read0013797 read0013797 Scopus Author ID 7202640559 7202640559 著者名 Masuzawa, Toshimitsu
キーワード等	Derandomization
	Fault-tolerance
	Graph sketch
	Labeling scheme
内容	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.
抄録	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.
出版者	Springer Science and Business Media Deutschland GmbH
収録物名	Distributed Computing
巻(号)	38(1)
ページ	31-50
刊行年月	2024-11-04
言語	英語
ハンドルURL	https://hdl.handle.net/11094/98811
PISSN	01782770
eISSN	14320452
関連情報 (isIdenticalTo)	DOI (出版社版) https://doi.org/10.1007/s00446-024-00472-6
アクセス権	open access
権利情報	This article is licensed under a Creative Commons Attribution 4.0 International License.
出版タイプ	Version of Record
カテゴリ	学術雑誌論文 Journal Article

資源タイプ	学術雑誌論文
ローカル資源タイプ	学術雑誌論文
DCTERMS.bibliographicCitation	Distributed Computing. 2024, 38(1), p. 31-50
DC.title	Deterministic fault-tolerant connectivity labeling scheme
DC.creator	Izumi, Taisuke
	Emek, Yuval
	Wadayama, Tadashi
	Masuzawa, Toshimitsu
DC.publisher	Springer Science and Business Media Deutschland GmbH
DC.language' scheme='DCTERMS.RFC1766	英語
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2024-11-04
DC.identifier	https://doi.org/10.1007/s00446-024-00472-6
DC.subject	Derandomization
	Fault-tolerance
	Graph sketch
	Labeling scheme
DC.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.
DCTERMS.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.
DC.rights	This article is licensed under a Creative Commons Attribution 4.0 International License.
DC.format	98811
citation_title	Deterministic fault-tolerant connectivity labeling scheme
citation_author	Izumi, Taisuke
	Emek, Yuval
	Wadayama, Tadashi
	Masuzawa, Toshimitsu
citation_publisher	Springer Science and Business Media Deutschland GmbH
citation_language	英語
citation_date	2024-11-04
citation_journal_title	Distributed Computing
citation_volume	38
citation_issue	1
citation_firstpage	31
citation_lastpage	50
citation_doi	https://doi.org/10.1007/s00446-024-00472-6
citation_public_url	https://hdl.handle.net/11094/98811

Deterministic fault-tolerant connectivity labeling scheme

閲覧可能ファイル

論文情報

論文詳細を表示