Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel
Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel
复制标题
动态多址信道冲突解决的快速非自适应确定性算法
DOI：
10.1137/140982763
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
D. Kowalski
中科院分区：
文献类型：
--
作者：
G. D. Marco;D. Kowalski
一个经典的问题，在解决一个分散的多址信道是解决冲突时，一组站试图在同一时间在一个共享的通信信道上发送。在静态场景中，即，当所有站同时激活时，Komlos和Greenberg [IEEE Trans. Inform. Theory，31（1985），pp. 302- 306]在他们的开创性工作表明，它是可能的，以解决冲突之间的$k$站从一个合奏的$n$，在时间$O（k + k \log（n/k））$在最坏的情况下，一个非自适应确定性算法。在本文中，我们表明，在一个动态的情况下，当站可以加入信道在任意轮，有一个非自适应的确定性算法，保证每个站的成功传输，只有稍微大的时间：O（k\log n\log\log n）$在最坏的情况下。这几乎与Greenberg和Winograd的$\Omega（k\log n/\log k）$下限相匹配[J. ACM，32（1985），pp. 589--596]，甚至在更强的设置：自适应算法...
A classical problem in addressing a decentralized multiple-access channel is resolving conflicts when a set of stations attempt to transmit at the same time on a shared communication channel. In a static scenario, i.e., when all stations are activated simultaneously, Komlos and Greenberg [IEEE Trans. Inform. Theory, 31 (1985), pp. 302--306] in their seminal work showed that it is possible to resolve the conflict among $k$ stations from an ensemble of $n$, with a nonadaptive deterministic algorithm in time $O(k + k \log(n/k))$ in the worst case. In this paper we show that in a dynamic scenario, when the stations can join the channel at arbitrary rounds, there is a nonadaptive deterministic algorithm guaranteeing a successful transmission for each station in only a slightly bigger time: $O(k\log n\log\log n)$ in the worst case. This almost matches the $\Omega(k\log n/\log k)$ lower bound by Greenberg and Winograd [J. ACM, 32 (1985), pp. 589--596] that holds even in much stronger settings: for adaptive algor...
多路访问信道上的对抗性排队
影响因子：
1.3
作者：
Chlebus B
通讯作者：
Chlebus B