论文标题
共享渠道上的确定性非自适应争夺解决方案
Deterministic non-adaptive contention resolution on a shared channel
论文作者
论文摘要
在多个访问渠道中，自主站能够传输和收听共享设备。一个称为\ textIt {争论解决方案}的基本问题是允许任何站通过解决同时发送时出现的冲突来成功传达其信息。尽管在此问题上有很长的历史，但大多数结果都涉及所有站点同时启动时静态设置，而在现实情况下，当电台可以在任意时间加入渠道时，许多基本问题仍然打开。 在本文中，我们探讨了三个主要渠道特征（站点之间的异步，对竞争者数量的知识以及成功传输后关闭电台的可能性）可能对非自适应确定性算法的时间复杂性产生的影响。我们建立了上限和下限，允许了解哪些参数允许及时的争议解决方案，哪些参数不得。
In a multiple access channel, autonomous stations are able to transmit and listen to a shared device. A fundamental problem, called \textit{contention resolution}, is to allow any station to successfully deliver its message by resolving the conflicts that arise when several stations transmit simultaneously. Despite a long history on such a problem, most of the results deal with the static setting when all stations start simultaneously, while many fundamental questions remain open in the realistic scenario when stations can join the channel at arbitrary times. In this paper, we explore the impact that three major channel features (asynchrony among stations, knowledge of the number of contenders and possibility of switching off stations after a successful transmission) can have on the time complexity of non-adaptive deterministic algorithms. We establish upper and lower bounds allowing to understand which parameters permit time-efficient contention resolution and which do not.
