Multi Version Coding An Information Theoretic Perspective of Consistent Distributed Storage
In applications of distributed storage systems to distributed computing and implementation of key value stores, the following property, usually referred to as consistency in distributed computing, is an important requirement: as the data stored changes, the latest version of the data must be accessible to a client that connects to the storage system. Motivated by technological trends where key value stores are increasingly implemented in high speed memory, an information theoretic formulation called multi version coding is introduced in this paper in order to understand and minimize the memory overhead of consistent distributed storage. Multi version coding is characterized by <inline formula> <tex math notation="LaTeX"\nu$ /tex math>/inline formula> totally ordered versions of a message and a storage system with <inline formula> <tex math notation="LaTeX"$n$ /tex math>/inline formula> servers. At each server, values corresponding to an arbitrary subset of the <inline formula> <tex math notation="LaTeX"\nu$ /tex math>/inline formula> versions are received and encoded. For any subset of <inline formula> <tex math notation="LaTeX"$c$ /tex math>/inline formula> servers in the storage system, the value corresponding to the latest common version or a later version, as per the total ordering, among the <inline formula> <tex math notation="LaTeX"$c$ /tex math>/inline formula> servers is required to be decodable. An achievable multi version code construction via linear coding and a converse result that shows that the construction is asymptotically tight when <inline formula> <tex math notation="LaTeX"\nu (c 1) /tex math>/inline formula> are provided. An implication of the converse is that there is an inevitable price, in terms of storage cost, to ensure consistency in distributed storage systems.
IEEE Transactions on Information Theory