文章基本信息

标题：Fast Deterministic Algorithms for Highly-Dynamic Networks
本地全文：下载
作者：Keren Censor-Hillel ; Neta Dafni ; Victor I. Kolobov 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：184
页码：28:1-28:16
DOI：10.4230/LIPIcs.OPODIS.2020.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which arbitrarily many edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an O(1) amortized time complexity, (2) using only O(log{n})-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, (degree 1)-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.
关键词：dynamic distributed algorithms