The Cost of Synchronizing Multiple-Access Channels
The Cost of Synchronizing Multiple-Access Channels
复制标题
同步多路访问信道的成本
DOI：
10.1145/2767386.2767439
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Grzegorz Stachowiak
中科院分区：
文献类型：
--
作者：
T. Jurdzinski;Grzegorz Stachowiak
多址信道是一种多个用户（也称为站）可以交换信息的通信模型。由于它提供有限的容量，通过它发送的一些信息可能会由于信号干扰（冲突）而丢失。因此，成功地将消息传递到站点需要打破信道上的对称性。在这项工作中，我们考虑的非同步信道的信道同步问题：假设站与消息唤醒动态的信道上，什么是最小（预期）的时间需要所有站接收至少一个消息。历史上，第一个被认为是“经典”的信道假设，只要两个或更多个站同时发送，发送的信息就会丢失，否则它会被传递到所有站。在开创性的论文中，Kushilevitz和Mansour证明了在具有n个竞争站的信道上的第一次成功传输在最坏的情况下可能需要Ω（log n）期望的任何协议的通信回合。然而，结果是在假设所有竞争者在同一轮开始他们的协议的情况下成立的。我们证明，在更一般的情况下，其中的站可能有不同的本地时钟，并在任意时间启动协议，下限增加二次Ω（log 2 n）预期轮。这两个下界匹配相应的算法在以前的论文。因此，我们的下界证明了多项式的影响，同步的经典多址信道。最近，基于信号干扰噪声比（SINR）的更精确的信道被提出和研究。基于SINR的信道的优点在于，除了更接近实际的物理场景之外，可以在单轮中调度一些更苛刻的通信模式。我们支持这种直觉表明，在这样的信道上传递的消息可以做得更快，比在经典的信道上，主要是在O（log 2 n/log log n）的预期轮数，从而分离的经典信道模型的SINR的。(The同样的时间限制也具有很高的概率）。最后，我们证明了对于确定性协议，在SINR信道上接收消息需要时间Ω（n），如果站点可以访问全局时钟，则时间Ω（n）惊人地几乎呈指数下降到O（log 2 n），这也将SINR信道与经典信道分开，由于后者的下限Ω（n log n）。我们还匹配后者的界限相应的下限。这与我们的O（log 2/log log n）轮随机算法，也证明了同步问题的确定性和随机解决方案之间的差距。
Multiple access channel is a communication model in which many users, also called stations, could exchange information. Since it offers limited capacity, some information sent through it might be lost due to signal interference (collision). Therefore, successful message delivery to a station requires breaking symmetry on the channel. In this work we consider the channel-synchronization problem on non-synchronized channels: assuming stations with messages wake-up dynamically on the channel, what is the minimum (expected) time needed for all stations to receive at least one message each. Historically, the first considered "classical" channel assumed that whenever two or more stations transmit simultaneously, the transmitted information is lost, otherwise it is delivered to all stations. In the seminal paper, Kushilevitz and Mansour proved that the first successful transmission on the channel with n contending stations may require, in the worst case, Ω(log n) expected communication rounds for any protocol. The result, however, holds under assumption that all contenders start their protocols at the same round. We prove that in more general scenario, in which the stations may have different local clocks and start the protocol at arbitrary times, the lower bound increases quadratically to Ω(log2 n) expected rounds. Both lower bounds are matched by corresponding algorithms developed in previous papers. Therefore, our lower bound proves the polynomial impact of synchronization on the classical multiple-access channels. Recently, more accurate channels based on Signal to Interference and Noise Ratio (SINR) were proposed and studied. The advantage of the SINR-based channel is that, apart of being closer to realistic physical scenario, some more demanding communication patterns could be scheduled in a single round. We support this intuition by showing that on such channel delivery of a message could be done faster than on the classical channel, mainly, in O(log2 n/log log n) expected number of rounds, thus separating the classical channel model from the SINR one. (The same time bound also holds with high probability.) Finally, we prove that for deterministic protocols receiving a message on the SINR channel requires time Ω(n), which surprisingly drops nearly exponentially to O(log2 n) if the stations have access to the global clock, which also separates SINR channel from the classic one, due to the lower bound Ω(n log n) on the latter. We also match the latter bound by corresponding lower bound. This together with our O(log2/log log n) round randomized algorithm, also proves a gap between deterministic and randomized solutions to the synchronization problem.