Anonymous Daemon Conversion in Self-stabilizing Algorithms by Randomization in Constant Space

Anonymous Daemon Conversion in Self-stabilizing Algorithms by Randomization in Constant Space
复制标题

恒定空间随机化自稳定算法中的匿名守护进程转换

DOI：
--
复制
发表时间：
2008
期刊：
International Conference of Distributed Computing and Networking
影响因子：
--
通讯作者：
P. Srimani
P. Srimani
中科院分区：
--
文献类型：
--
作者：
W. Goddard;S. Hedetniemi;D. P. Jacobs;P. Srimani

文献摘要

被引文献

相似文献

我们提出了一个广义的计划，可以转换成一个随机的自稳定下一个分布式守护进程，只使用恒定的额外空间，没有ID的任何算法，在一个不公平的中央守护进程的自稳定。如果原始算法是匿名的，那么所得到的自稳定算法也是匿名的。我们提供了一个详细的复杂度分析，表明预期的减速是O（n3）的上限。
We propose a generalized scheme that can convert any algorithm that self-stabilizes under an unfair central daemon into a randomized one that self-stabilizes under a distributed daemon, using only constant extra space and without IDs. If the original algorithm is anonymous the resulting self-stabilizing algorithm is also anonymous. We provide a detailed complexity analysis that show that the expected slowdown is upper bounded by O(n3).