Fundamental Limits of Distributed Linear Encoding

Nastaran Abadi Khooshemehr, Mohammad Ali Maddah-Ali

Research output: Contribution to journalArticlepeer-review

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, 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, comprised of a set of K ∈ N isolated source nodes and N ∈ 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 the adversarial nodes, denoted by β ∈ N, and the cardinality of the set of symbols that each one generates, denoted by v∈ N, the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of t ∈ N encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is t*∈ N, the minimum of such t, which is a function of K, N, β, and v. In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that t*Linear =K+2 β (v-1), if N ≥ K+2 β (v-1), and t*Linear}}=N, if N ≤ K+2 β (v-1). In order to achieve t*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. In order to prove 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.

Original languageEnglish (US)
Pages (from-to)7985-7998
Number of pages14
JournalIEEE Transactions on Information Theory
Volume67
Issue number12
DOIs
StatePublished - Dec 1 2021
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 1963-2012 IEEE.

Keywords

  • Distributed systems
  • blockchain
  • distributed encoding
  • sharding

Fingerprint

Dive into the research topics of 'Fundamental Limits of Distributed Linear Encoding'. Together they form a unique fingerprint.

Cite this