Randomized mutual exclusion algorithms revisited
Randomized mutual exclusion algorithms revisited
复制标题
重新审视随机互斥算法
DOI：
10.1145/135419.135468
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
M. Rabin
中科院分区：
文献类型：
--
作者：
E. Kushilevitz;M. Rabin
在文[4]中，利用一个对数大小的共享变量，给出了一个有界等待互斥的随机算法。Saias和Lynch[5]指出，上述假设的对抗性调度器可以观察到从临界段打开到下一个临界段关闭这段时间内进程的行为。然后，它可以得出关于它们的局部变量的值以及共享变量的随机舍入分量的值的结论，并安排时间表以区别于所选的过程。这将使该算法所声称的属性无效。
本文利用文[4]的思想，对文[4]中的算法进行了改进，克服了这一困难，得到了基本相同的结果。因此，就像在[4]中一样，随机化产生了具有有限等待的互斥的简单算法，其采用的共享变量的大小比[1]中为确定性算法建立的下界小得多。
In [4] a randomized algorithm for mutual exclusion with bounded waiting, employing a logarithmic sized shared variable, was given. Saias and Lynch [5] pointed out that the adversary scheduler postulated in the above paper can observe the behavior of processes in the interval between an opening of the critical section and the next closing of the critical section. it can then draw conclusions about values of their local variables as well as the value of the randomized round number component of the shared variable, and arrange the schedule so as to discriminate against a chosen process. This invalidates the claimed properties of the algorithm.
In the present paper the algorithm in [4] is modified, using the ideas of [4], so as to overcome this difficulty, obtaining essentially the same results. Thus, as in [4], randomization yields simple algorithms for mutual-exclusion with bounded waiting, employing a shared variable of considerably smaller size than the lower-bound established in [1] for deterministic algorithms.