Coded Caching for Distributed Storage

Content delivery networks store information distributed across multiple servers, so as to balance the load and avoid unrecoverable losses in case of node or disk failures. Coded caching has been shown to be a useful technique which can reduce peak traffic rates by pre-fetching popular content at the end users and encoding transmissions so that different users can extract different information from the same packet. On one hand, distributed storage limits the capability of combining content from different servers into a single message, causing performance losses in coded caching schemes. But, on the other hand, the inherent redundancy existing in distributed storage systems can be used to improve the performance of those schemes through parallelism. This paper designs coded caching and delivery schemes tailored towards systems where the library is distributed across multiple servers, possibly with some redundancy in the form of maximum distance separable (MDS) erasure codes. Different schemes are proposed based on the capacity of the users' caches, as well as the number of parity servers. The main focus is on scenarios with one (RAID-4) or two (RAID-6) parity servers, but the paper also includes simple extensions for cases with more than two or no parity servers at all. The proposed schemes are shown to reduce the worst case latency, or equivalently the peak transmission rate from any server, below that of state-of-the-art algorithms