Only a single example is known of a regenerating code with both small field size and efficient repair, and with parameters in a corner point on the cutset bound different from the MSR and MBR points. Here we present another such code, based on a vector space partition of a 9-dimensional binary space into 73 subspaces of dimension 3 that is strongly related to the projective plane PG(2, 8); the coding spaces of the code consist of 72 of the subspaces in the partition. The new storage code comes with an efficient repair algorithm that can be described in terms of the underlying geometry.

In a distributed storage system serving hot data, the data recovery performance becomes important, captured e.g. by the service rate. We give partial evidence for it being hardest to serve a sequence of equal user requests (as in PIR coding regime) both for concrete and random user requests and server contents. We prove that a constant request sequence is locally hardest to serve: If enough copies of each vector are stored in servers, then if a request sequence with all requests equal can be served then we can still serve it if a few requests are changed. For random iid server contents, with number of data symbols constant (for simplicity) and the number of servers growing, we show that the maximum number of user requests we can serve divided by the number of servers we need approaches a limit almost surely. For uniform server contents, we show this limit is 1/2, both for sequences of copies of a fixed request and of any requests, so it is at least as hard to serve equal requests as any requests. For iid requests independent from the uniform server contents the limit is at least 1/2 and equal to 1/2 if requests are all equal to a fixed request almost surely, confirming the same. As a building block, we deduce from a 1952 result of Marshall Hall, Jr. on abelian groups, that any collection of half as many requests as coded symbols in the doubled binary simplex code can be served by this code. This implies the fractional version of the Functional Batch Code Conjecture that allows half-servers.

Update performance is a common concern in modern distributed storage systems. In this work, we construct explicit update-efficient codes via finite projective planes, also having efficient local repair with availability, and a short description. We compare to other existing solutions, including block codes from convolutional codes.We analyze the repair behavior of the codes via analogy with decoding of LDPC codes over an erasure channel, and the performance of the distributed storage system based on the codes involving updates and repairs.

We propose a new model of asynchronous batch codes that allow for parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when requests arrive at random times and they take varying time to process. We show that the graph-based batch codes studied by Rawatet al.are asynchronous. Further, we demonstrate that hypergraphs of Berge girth larger or equal to 4, respectively larger or equal to 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove a hypergraph-theoretic proposition that the maximum number of hyperedges in a hypergraph of a fixed Berge girth equals the quantity in a certain generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown, Erdős and Sós. We then apply the constructions and bounds by Erdős, Frankl and Rödl about this generalization of the (6,3)-problem, known as the ($3\varrho $-3,$\varrho $)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. We derive bounds on the optimal redundancy of several families of asynchronous batch codes with the query size$t=2$. In particular, we show that the optimal redundancy$\rho (k)$of graph-based asynchronous batch codes of dimension$k$for$t=2$is$2\sqrt {k}$. Moreover, for graph-based asynchronous batch codes with$t \ge 3$,$\rho (k) = O\left ({{k}^{1/(2-\epsilon)}}\right)$for any small$\epsilon >0$.

We propose a new model of asynchronous batch codes that allow for parallel recovery of information symbols from a coded database in an asynchronous manner, i.e. when different queries take different time to process. Then, we show that the graph-based batch codes studied by Rawat et al. are asynchronous. Further, we demonstrate that hypergraphs of Berge girth at least 4, respectively at least 3, yield graph-based asynchronous batch codes, respectively private information retrieval (PIR) codes. We prove the hypergraph-theoretic proposition that the maximum number of hyperedges in a hypergraph of a fixed Berge girth equals the quantity in a certain generalization of the hypergraph-theoretic (6,3)-problem, first posed by Brown, Erdos and Sós. We then apply the constructions and bounds by Erdos, Frankl and Rödl about this generalization of the (6,3)problem, known as the (3r-3,r)-problem, to obtain batch code constructions and bounds on the redundancy of the graph-based asynchronous batch and PIR codes. Finally, we show that the optimal redundancy ρ(k) of graph-based asynchronous batch codes of dimension k with the query size t = 3 is 2√k. Moreover, for a general fixed value of t ≥ 4, ρ(k) = O (k1/(2-ε)) for any small ε > 0. For a general value of t ≥ 4, limk→∞ρ(k)√k = ∞.

We develop a general framework to prove Kraft-type inequalities for prefix-free permutation codes for source coding with various notions of permutation code and prefix. We also show that the McMillan-type converse theorem in most of these cases fails, and give a general form of a counterexample. Our approach is more general and works for other structures besides permutation codes. The classical Kraft inequality for prefix-free codes and results about permutation codes follow as corollaries of our main theorem and main counterexample.

New bounds on the cardinality of permutation codes equipped with the Ulam distance are presented. First, an integer-programming upper bound is derived, which improves on the Singleton-type upper bound in the literature for some lengths. Second, several probabilistic lower bounds are developed, which improve on the known lower bounds for large minimum distances. The results of a computer search for permutation codes are also presented.