Self-stabilizing MIS computation in the beeping model

doi:10.1007/s00446-025-00497-5

Self-stabilizing MIS computation in the beeping model

2025-12-19

0

PRE

AI

DOI：10.1007/s00446-025-00497-5

原文链接

原文求助

摘要

En 中文

我们考虑在极其弱化的鸣叫通信模型中计算极大独立集（MIS）的自稳定算法。我们假设顶点对网络拓扑有一定的了解。我们重新审视了由Jeavons、Scott和Xu（2013）提出的非自稳定算法，该算法在鸣叫模型中计算MIS。我们改进该算法使其自稳定，并探索了三种不同变体，这些变体在顶点可用的拓扑知识和鸣叫信道数量上有所不同。在第一种变体中，每个顶点都知道图中最大度数\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta$$\end{document}的上界。对于此情况，我们证明所提出的自稳定版本保持了与原始算法相同的运行时间，即以高概率（w.h.p.）在任意n顶点图上经过\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document}轮后稳定。在第二种变体中，每个顶点仅知道其自身度数的上界。对于此情况，我们证明该算法以高概率在任意n顶点图上经过\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n\cdot \log \log n)$$\end{document}轮后稳定。在第三种变体中，我们考虑具有两个鸣叫信道的模型，其中每个顶点都知道其1跳邻域内节点最大度数的上界。我们证明该变体以高概率在\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document}轮后稳定。

Keyword:

Maximal independent set

Self-stabilization

Beeping model

Self-stabilizing MIS computation in the beeping model

摘要

期刊

机构

引用论文