论文标题
分布式编码的基本限制
Fundamental Limits of Distributed Encoding
论文作者
论文摘要
在一般编码理论中，我们经常假设在传输或存储编码符号时观察到错误，而编码本身的过程是没有错误的。由编码理论的最新应用激励，在本文中，我们考虑了编码过程分布并容易出错的情况。我们介绍了分布式编码的问题，包括$ k \ in \ mathbb {n} $孤立的源节点和$ n \ in \ mathbb {n} $编码节点。每个源节点都有一个来自有限字段的符号，并将其发送到所有编码节点。每个编码节点都存储一个编码的符号，作为接收符号的函数。但是，某些源节点由对手控制，并可能向不同的编码节点发送不同的符号。取决于\ mathbb {n} $中$β\表示的对抗性节点的数量，以及每个生成的符号的数量，用$ v \ in \ mathbb {n} $表示，是不可能的。假设一个解码器连接到\ Mathbb {n} $编码节点的$ t \的任意子集，并希望正确解码诚实节点的符号，而无需识别诚实和对抗性节点的集合。在本文中，我们研究了$ t^*\ in \ mathbb {n} $，最低$ t $，它的函数是$ k $，$ n $，$β$和$ v $。我们表明，当编码节点使用线性编码时，$ t^*_ {\ textrm {linear}} = k+2β（v-1）$，如果$ n \ ge k+2β（v-1）$，和$ t^*_ {\ textrm {linear}}} = n $，if $ n \ k+k+2β（v-1）为了实现$ t^*_ {\ textrm {linear}} $，我们使用随机线性编码并显示在解码器找到的任何可行解决方案中，诚实节点的消息正确解码。对于基本限制的相反，我们表明，当对手以特定的方式行事时，它总是会混淆两个可行解决方案之间的解码器，这些解决方案在至少一个诚实节点的信息中有所不同。
In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprising of $K\in\mathbb{N}$ isolated source nodes and $N\in\mathbb{N}$ encoding nodes. Each source node has one symbol from a finite field and sends it to all encoding nodes. Each encoding node stores an encoded symbol, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of adversarial nodes, denoted by $β\in\mathbb{N}$, and the number of symbols that each one generates, denoted by $v\in\mathbb{N}$, the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in\mathbb{N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. In this paper, we study $t^*\in\mathbb{N}$, the minimum of $t$, which is a function of $K$, $N$, $β$, and $v$. We show that when the encoding nodes use linear coding, $t^*_{\textrm{linear}}=K+2β(v-1)$, if $N\ge K+2β(v-1)$, and $t^*_{\textrm{linear}}=N$, if $N\le K+2β(v-1)$. In order to achieve $t^*_{\textrm{linear}}$, we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. For the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node.
