Dynamic sharing of a multiple access channel
Dynamic sharing of a multiple access channel
复制标题
多路访问信道的动态共享
DOI：
10.4230/lipics.stacs.2010.2446
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Kowalski
中科院分区：
文献类型：
--
作者：
Marcin Bienkowski;M. Klonowski;M. Korzeniowski;D. Kowalski
本文研究了多址信道上的互斥问题。互斥是分布式计算的基本问题之一。在这个问题的经典版本中，n个进程执行一个并发程序，该程序偶尔会触发其中一些进程使用共享资源，如内存、通信通道、设备等。目标是设计一个分布式算法来控制进出共享资源的入口和出口，这样在任何时候都最多有一个进程访问它。我们考虑经典的互斥和稍弱的互斥，称为ep-互斥，其中对于一个过程停留在临界区域的每一个周期，临界区域内存在其他过程的概率最多为ep。我们表明，在某些信道设置中，经典互斥即使对于随机算法也是不可行的，而ep互斥是可行的。在更宽松的信道设置下，我们证明了经典互斥问题的最大跨度复杂度与其较弱的ep-不相容版本之间存在指数差距。我们还展示了如何保证互斥算法的公平性，即每个想要进入临界区的进程最终都会成功。
In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes perform a concurrent program which occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource in such a way that in any time there is at most one process accessing it. We consider both the classic and a slightly weaker version of mutual exclusion, called ep-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most ep. We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while ep-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker ep-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.