Self-stabilizing mutual exclusion using unfair distributed scheduler
Self-stabilizing mutual exclusion using unfair distributed scheduler
复制标题
使用不公平分布式调度器的自稳定互斥
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
A. Datta;M. Potop;S. Tixeuil
一个自稳定算法，无论初始系统状态，收敛到一组状态，满足合法性谓词，而不需要显式异常处理程序的向后恢复无限的时间。互斥是分布式计算领域的基础，通过串行化对公共共享资源的访问。所有现有的设计用于不公平分布式调度器下的概率自稳定互斥算法都存在以下共同缺点：一旦稳定，给定节点上两次执行临界部分之间不存在时间上限。我们提出了第一个概率自稳定算法，保证这样的界限（O（n/sup 3/），其中n是网络的大小），同时使用不公平的分布式调度。随着调度对手变得越来越弱，界限变得越来越好。我们的算法工作在一个匿名的单向环的任何大小，并有一个O（n/sup 3/）的预期稳定时间。
A self-stabilizing algorithm, regardless of the initial system state, converges infinite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. Mutual exclusion is fundamental in the area of distributed computing, by serializing the accesses to a common shared resource. All existing probabilistic self-stabilizing mutual exclusion algorithms designed to work under an unfair distributed scheduler suffer from the following common drawback: Once stabilized, there exists no upper bound of time between two executions of the critical section at a given node. We present the first probabilistic self-stabilizing algorithm that guarantees such a bound (O(n/sup 3/), where n is the network size) while working using an unfair distributed scheduler. As the scheduling adversary gets weaker the bound gets better. Our algorithm works in an anonymous unidirectional ring of any size and has a O(n/sup 3/) expected stabilization time.