Scholarlink

<p>We consider self-stabilizing algorithms to compute a Maximal Independent Set (MIS) in the extremely weak <i>beeping</i> communication model. We assume that vertices have some knowledge about the topology of the network. We revisit the not self-stabilizing algorithm proposed by Jeavons, Scott, and Xu (2013), which computes an MIS in the beeping model. We enhance this algorithm to be self-stabilizing, and explore three different variants, which differ in the knowledge about the topology available to the vertices and the number of beeping channels. In the first variant, every vertex knows an upper bound on the maximum degree <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\Delta\)</EquationSource> </InlineEquation> of the graph. For this case, we prove that the proposed self-stabilizing version maintains the same run-time as the original algorithm, i.e., it stabilizes after <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O(\log n)\)</EquationSource> </InlineEquation> rounds w.h.p. on any <i>n</i>-vertex graph. In the second variant, each vertex only knows an upper bound on its own degree. For this case, we prove that the algorithm stabilizes after <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(O(\log n\cdot \log \log n)\)</EquationSource> </InlineEquation> rounds on any <i>n</i>-vertex graph, w.h.p. In the third variant, we consider the model with two beeping channels, where every vertex knows an upper bound of the maximum degree of the nodes in the 1-hop neighborhood. We prove that this variant stabilizes w.h.p. after <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(O(\log n)\)</EquationSource> </InlineEquation> rounds.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Self-stabilizing MIS computation in the beeping model

  • 期刊论文

  • 发表日期：

    2025年12月19日

查看全文
  • George Giakkoupis,
  • Volker Turau,
  • Isabella Ziccardi

摘要

We consider self-stabilizing algorithms to compute a Maximal Independent Set (MIS) in the extremely weak beeping communication model. We assume that vertices have some knowledge about the topology of the network. We revisit the not self-stabilizing algorithm proposed by Jeavons, Scott, and Xu (2013), which computes an MIS in the beeping model. We enhance this algorithm to be self-stabilizing, and explore three different variants, which differ in the knowledge about the topology available to the vertices and the number of beeping channels. In the first variant, every vertex knows an upper bound on the maximum degree \(\Delta\) of the graph. For this case, we prove that the proposed self-stabilizing version maintains the same run-time as the original algorithm, i.e., it stabilizes after \(O(\log n)\) rounds w.h.p. on any n-vertex graph. In the second variant, each vertex only knows an upper bound on its own degree. For this case, we prove that the algorithm stabilizes after \(O(\log n\cdot \log \log n)\) rounds on any n-vertex graph, w.h.p. In the third variant, we consider the model with two beeping channels, where every vertex knows an upper bound of the maximum degree of the nodes in the 1-hop neighborhood. We prove that this variant stabilizes w.h.p. after \(O(\log n)\) rounds.