论文标题
最大独立的自动稳定和拜占庭公差
Self-stabilization and byzantine tolerance for maximal independent
论文作者
论文摘要
我们分析了瞬态和拜占庭断层对一般网络中最大独立集的构建的影响。我们适应了Turau`用于计算此类顶点集的自动稳定算法。我们的算法是自动稳定的，并且在任意拜占庭断层的更困难的背景下也起作用。 拜占庭节点可以防止其附近的节点参与独立集的任意时间。我们通过关注距离1或更小的拜占庭节点的节点的所有节点的集合，从而对其影响进行边界，并排除距离2处的某些节点。据我们所知，我们介绍了第一个算法在合理的分布式守护程序下均能耐受瞬时和拜占庭的断层。 我们证明，该算法在$ \ Mathcal O（ΔN）$ rounds W.H.P.中收敛，其中$ n $和$δ$是网络的大小和最高度，resp。此外，我们为对抗性分布式守护程序下的匿名系统提出了此算法的修改版本 $ \ MATHCAL O（N^{2}）$预期的步骤数。
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 of 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$ and $Δ$ are the size and the maximum degree of the network, resp. Additionally, we present a modified version of this algorithm for anonymous systems under the adversarial distributed daemon that converges in $ \mathcal O(n^{2})$ expected number of steps.
