文件名称：A Self-Stabilizing Algorithm for Maximal Matching in Anonymous Networks
文件大小：247KB
文件格式：PDF
更新时间：2020-01-20 05:25:00
自稳定算法 最大匹配 匿名网络
We propose a self-stabilizing algorithm for computing a maximal matching in an anony- mous network. The complexity is O(n2) moves with high probability, under the ad- versarial distributed daemon. Among all adversarial distributed daemons and with the anonymous assumption, our algorithm provides the best known complexity. Moreover, the previous best known algorithm working under the same daemon and using identity has a O(m) complexity leading to the same order of growth than our anonymous al- gorithm. Finally, we do not make the common assumption that a node can determine whether one of its neighbors points to it or to another node, and still we present a solution with the same asymptotic behavior.