Observations on self-stabilizing graph algorithms for anonymous networks
Observations on self-stabilizing graph algorithms for anonymous networks
复制标题
匿名网络自稳定图算法的观察
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
S. Ravi
中科院分区：
文献类型：
--
作者：
S. Shukla;D. Rosenkrantz;S. Ravi
本文研究了连通无向图上若干问题的确定性一致自稳定算法的存在性。本研究是在三种并行模型下进行的，即中央守护进程、限制并行和最大并行。我们观察到，对于2-着色奇度完全二部图、2-着色树、确定一般图的极大独立集、平面图的有效着色等问题，在极大并行模型下不存在DUSSA.在中心守护进程模型下，平面图的6-着色问题的DUSSA在GK 93中给出。对于上面列出的其他问题，我们在中央守护进程模型下提出了DUSSA。我们观察到，这些DUSSA的工作正常下，以及一个受限制的并行模型。这一事实使我们能够应用SRR 94]中的一种技术来获得上述所有问题在最大随机性模型下的随机化USSA（RUSSA）。这些RUSSA以概率1实现自稳定。我们还观察到，由于Angluin Ang 80]的技术导致一般的结果，建立不存在的DUSSA的一个大集合的图形问题下的任何并行模型。这个集合中的问题包括确定图中节点数的奇偶性和各种图类（例如，平面图，弦图和区间图）的成员资格测试。
We investigate the existence of deterministic uniform self-stabilizing algorithms (DUSSAs) for a number or problems on connected undirected graphs. This investigation is carried out under three models of parallelism, namely central daemon, restricted parallelism, and maximal paral-lelism. We observe that for several problems including 2-coloring odd-degree complete bipartite graphs, 2-coloring trees, nding maximal independent sets in general graphs, and obtaining a valid coloring of planar graphs, no DUSSAs exist under the maximal parallelism model. A DUSSA for the 6-coloring problem for planar graphs under the central daemon model was presented in GK93]. For the other problems listed above, we present DUSSAs under the central daemon model. We observe that these DUSSAs work correctly under a restricted parallelism model as well. This fact enables us to apply a technique in SRR94] to obtain randomized USSAs (RUSSAs) under the maximal paral-lelism model for all the above problems. These RUSSAs achieve self-stabilization with probability 1. We also observe that techniques due to Angluin Ang80] lead to general results that establish the non-existence of DUSSAs for a large collection of graph problems under any of the parallelism models. The problems in this collection include determining the parity of the number of nodes in a graph and membership testing for various graph classes (for example, planar graphs, chordal graphs, and interval graphs).