2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.9.3 | ||
| Paper Title | Fundamental limits of distributed encoding | ||
| Authors | Nastaran Abadi Khooshemehr, Mohammad Ali Maddah-Ali, Sharif University of Technology, Iran | ||
| Session | M.9: Topics in Coding for Storage and Memories | ||
| Presentation | Lecture | ||
| Track | Coding for Storage and Memories | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | 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, we introduce the problem of distributed encoding which is comprised of a set 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, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, 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 $\beta \in \mathbb{N}$, and the cardinality of the set of symbols that each one generates, denoted by $v \in \mathbb{N}$, this would make the process of decoding from the encoded symbols impossible. Assume that a decoder connects to an arbitrary subset of $t \in \mathbb{N}$ encoding nodes and wants to decode the symbol of honest nodes correctly, without necessarily identify the sets of honest and adversarial nodes. In this paper, we characterize $t^* \in \mathbb{N}$, as the minimum of such $t$, as a function of $K$, $N$, $\beta$, and $v$. In particular, we show that for $\beta\geq 1, v\ge 2$, $t^*=K+\beta (v-1)+1$, if $N \geq K+\beta (v-1)+1 $, and $t^*=N$, if $N \le K+\beta (v-1)$. Moreover, in order to achieve $t^*$, linear encoding is not sufficient. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
