Coded computing has proved to be useful in distributed computing, and has addressed challenges such as straggler workers. We have observed that almost all coded computing systems studied so far consider a setup of one master and some workers. However, recently emerging technologies such as blockchain, internet of things, and federated learning introduce new requirements for coded computing systems. In these systems, data is generated (and probably stored) in a distributed manner, so central encoding/decoding by a master is not feasible and scalable. This paper presents a multi-master distributed coded computing system that consists ofk∈ N data owners andN∈ N workers, where data owners employ workers to do some computations on their data, as specified by a target functionfof degreed∈ N. As there is no central encoder, workers perform encoding themselves, prior to computation phase. The challenge in this system is the presence of adversarial data owners that do not know the data of honest data owners but cause discrepancies by sending different versions of data to different workers, which is detrimental to local encodings in workers. There are at most β ∈ N adversarial data owners, and each distributes at mostv∈ N different versions of data. Since the adversaries and their possibly colluded behavior are not known to workers and honest data owners, workers compute tags of their received data, in addition to their main computational task, and send them to data owners in order to help them in decoding. We introduce a tag function that allows data owners to partition workers into sets that previously had received the same data from all data owners. Then, we characterize the fundamental limit of this multi-master distributed coded computing system, denoted byt*, which is the minimum number of workers whose work can be used to correctly calculate the desired function of data of honest data owners. We show thatt*=vβd(K− 1) + 1, and present converse and achievable proofs.

Sharding, i.e. splitting the miners or validators to form and run several subchains in parallel, is known as one of the main solutions to the scalability problems of blockchains. The drawback is that as the number of miners expanding each subchain becomes small, it becomes vulnerable to security attacks. To solve this problem, a framework, named as Ployshard, has been proposed in which each validator verifies a coded combination of the blocks introduced by different subchains, thus helping to protect the security of all subchains. In this paper, we introduce an attack on Ployshard, called the discrepancy attack, which is the result of malicious nodes controlling a few subchains and dispersing different blocks to different nodes. We show that this attack undermines the security of Polyshard and is undetectable in its current setting.

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 \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 the 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}$, 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. An important characteristic of a distributed encoding system is$t^{*} \in \mathbb {N}$, the minimum of such$t$, which is a function of$K$,$N$,$\beta $, 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^{*}_{\textrm {Linear}}=K+2\beta (v-1)$, if$N\ge K+2\beta (v-1)$, and$t^{*}_{\textrm {Linear}}=N$, if$N\le K+2\beta (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. 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.

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 ∈ ℕ isolated source nodes and 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 β ∈ ℕ, and the cardinality of the set of symbols that each one generates, denoted by v ∈ ℕ, this would make the process of decoding from the encoded symbols impossible. Assume that a decoder connects to an arbitrary subset of t ∈ ℕ 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* ∈ ℕ, as the minimum of such t, as a function of K, N, β, and v. In particular, we show that for β ≥ 1, v ≥ 2, t* = K + β(v - 1) + 1, if N ≥ K + β(v -1) + 1, and t* = N, if N ≤ K + β(v - 1). Moreover, in order to achieve t*, linear encoding is not sufficient.

In this paper, we study the zero error capacity of the molecular delay channel when multiple molecule types are available at the transmitter. In the molecular delay channel, each transmitted molecule (of any type) is received by a delay of at most $k$ time slots. Depending on the number of molecules that the transmitter is allowed to release in each time slot, we consider the following three cases: (i) when the maximum number of the released molecules of each type in each time slot is restricted (ii) when the total number of the released molecules (regardless of their type) in each time slot is restricted, and (iii) when the transmitter can use only one molecule type (of its choice) in each time slot. We derive lower bounds on the zero-error capacity of the delay channel for each case, by proposing zero-error codes that are based on the results by Kovačević and Popovski. We also derive upper bounds on the zero-error capacity of the delay channel. In the first case, these bounds match and yield the exact capacity, while in the other two cases, the bounds are shown to be close numerically. Our numerical results show that as the number of available molecule types increases, the capacity of the system increases substantially, compared to using only one molecule type. Furthermore, it is shown that the lower and upper bounds on the zero-error capacity of the delay channel in the second case are generally close to the lower and upper bounds in the third case, respectively, indicating the closeness of the zero-error capacities of the two cases. This result enables one to design a simpler system by employing a high rate code that has only one molecule type in each slot (designed for the third case) in the channel of the second case, without much rate loss.