Deterministic coding for interactive communication
Deterministic coding for interactive communication
复制标题
交互式通信的确定性编码
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
L. Schulman
中科院分区：
文献类型：
--
作者：
L. Schulman
在导致当前几代计算机的速度和存储容量提高的因素中，有两个因素是突出的。首先是越来越多的并行度--无论是在实际的并行和分布式计算机中，还是在顺序机器的越来越多的组件中。第二是逻辑设备和线路的戏剧性小型化。第一个因素极大地放大了在任何计算期间执行的处理器间通信的数量，而第二个因素增加了影响传输的噪声水平。由于这些原因，并根据噪声的作用应该在物理过程的模型中被理解的基础上，最近确定以下问题为基本问题[10]。考虑这样一个问题，它的输入被通过通信链路连接的两个处理器分开；对于该问题，存在一个交互协议，该协议解决了在任何输入上的T个传输中的问题，前提是信道是无噪声的。如果信道上确实存在一些噪声，那么为了可靠地解决通信问题所需的传输次数会受到什么影响？我们描述了一种确定性的方法，用于在只有恒定减速的有噪声的信道上模拟无噪声信道协议。这类似于香农编码定理的一般交互协议，后者只涉及数据传输，即单向协议[11]。这一结果是由NSF博士后奖学金支持的研究。允许免费复制本材料的全部或部分内容，前提是复制副本不是为了直接商业利益而制作或分发，并提供ACM版权声明和出版物的标题及其日期，并通知复制是经计算机械协会许可的。以其他方式复制或重新发布，需要付费和/或特定许可。第25号ACM斯托克‘93-51931CA，美国01993 ACM 0-89791-591-71931000510747。。。S1.50证明了最近的工作，为交互协议提供了一种随机化的模拟方法。因此，香农定理在一般的相互作用情况下，除了常量因子外，在所有情况下都重现。随机化的方法从根本上不适合进一步的去随机化，确定性的解决方案完全不同。在本工作中，树码扮演了关键角色，最初由Wozencraft[13]考虑是为了在计算上高效地解码有噪声的数据传输。在它们的新设置中，树代码被重新解释为一种将高度交互的协议转换成行为类似于一对单向协议的方式，因此可以以高速率和可靠性Y来实现。
Two factors are prominent among those contributing to the increases in speed and storage capacity in current generations of computers. The first is increasing parallelism — whether in actual parallel and distributed computers, or among the steadily more numerous components of a sequential machine. The second is the dramatic miniaturization of logical devices and wires. The first of these factors greatly magnifies the number of interprocessor communications performed during any computation, while the second increases the noise level affecting transmissions. For these reasons, and on the basis that the role of noise should be understood in a model of a physical process, the following concern was recently identified as basic [10]. Consider a problem whose input is split between two processors connect ed by a communication link; and for which an interactive protocol exists which solves the problem in T transmissions on any input, provided the channel is noiseless. If in fact there is some noise on the channel, what is the effect upon the number of transmissions needed in order to solve the communication problem reliably? We describe a deterministic method for simulating noiseless-channel protocols on noisy channels, with only a constant slow-down. This is an analog for general interactive protocols of Shannon’s coding theorem, which dealt only with data transmission, i.e. one-way protocols [11]. This result im*Research supported by an NSF postdoctoral fellowship. Permission to copy without fee all or part of this material is granted provided that the copias are not made or distributed for direct commercial advantage, the ACM copyright notice and tha title of the publication and its date appear, and notioe is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 25th ACM STOC ‘93-51931CA,USA 01993 ACM 0-89791 -591 -71931000510747 . .. S1.50 proves on recent work which provided a randomized simulation method for interactive protocols. The Shannon theorem is thus reproduced for the general interactive case, in all but the constant factor. The randomized method was fundamentally unsuited to further derandomization, and the deterministic solution is entirely different. A key role in the present work is played by tree codes, originally considered by Wozencraft [13] for the sake of comput ationally efficient decoding of noisy data transmissions. In their new setting tree codes are reinterpreted as a way of transforming a highly interactive protocol into one that behaves like a pair of one-way protocols, and which therefore can be implemented at both high rate and reliability y.