arXiv:2210.06116 · v4

Self-stabilization and Byzantine Tolerance for Maximal Independent Set

首次提交 2022-10-12 20:22

版本更新 2026-11-10 06:24

雷达观测 2026-11-11 11:04

摘要

We analyze the impact of transient and Byzantine faults on the construction of a maximal independent set in a general network. We adapt the self-stabilizing algorithm presented by Turau for computing such a vertex set. Our algorithm is self-stabilizing and also works under the more difficult context of arbitrary Byzantine faults. Byzantine nodes can prevent nodes close to them from taking part in the independent set for an arbitrarily long time. We give boundaries to their impact by focusing on the set of all nodes excluding nodes at distance 1 or less from Byzantine nodes, and excluding some of the nodes at distance 2. As far as we know, we present the first algorithm tolerating both transient and Byzantine faults under the fair distributed daemon. We prove that this algorithm converges in $\mathcal O(Δn)$ rounds w.h.p., where $n$ is the number of nodes and $Δ$ is the maximum degree of the network. Additionally, we present a modified version of this algorithm for anonymous systems under the adversarial distributed daemon that converges in $\mathcal O(n^{2})$ moves both in expected value and with high probability.

作者备注：it is an extented version of Self-stabilization and Byzantine Tolerance for Maximal Independent Set, Cohen, Johanne and Pilard, Laurence and S{é}nizergues, Jonas, in International Symposium on Stabilizing, Safety, and Security of Distributed Systems, 2021. arXiv admin note: substantial text overlap with arXiv:2111.08348