There are k files (say, elements of some fnite field) to be stored (redundantly) across n servers, n ≥ k. We assume wlog that the time to download a file from server m is exponential with rate μ_{m}, 1 ≤ m ≤ n, and that requests to download file i arrive at rate λ_{i}, 1 ≤ i ≤ k. Each server can store a linear combination of a (sub)set of files (encoded file), and thus can be used to help fulfill a request for any file in that subset.
The achievable service rate region of such a system is the set of request rate vectors (λ_{1},λ_{2},...,λ_{k}) that can be served so that no node is sent requests in excess of its service rate. Interestingly, the best schemes (those that maximize the achievable service rate
region) often combine replication and coding. We started looking into this problem in order to find when some complex queues that arise in distributed storage are stable. The problem turned out to be independently rich and connected to several other problems. Some aspects of the problem generalize batch coding, and some give rise to interesting questions in (fractional) graph theory.