On multi-version coding for distributed storage

The multi-version coding problem described previously by Wang and Cadambe is motivated by applications to distributed storage and computing. Here, we consider a modification to the previously described multi-version coding problem that retains the essence of the earlier definition, and show that our modification leads to a reduced storage cost. We consider a setting where there are n servers that aim to store ν versions of a message, where there is a total ordering on the versions from the earliest to the latest. We assume that each message version has size log₂ M bits. Each server can receive any subset of the ν versions and stores over an alphabet of size q a function of the message versions it receives. The (n, c, ν, M, q) multi-version code we consider ensures that, a decoder that connects to any c of the n servers can recover the message corresponding to the latest common version stored among those servers, or a message corresponding to a version that is later than the latest common version. Unlike our earlier paper, we allow for the message version that is decoded to be one that is later than the latest common version. Through an achievable scheme and a tight converse, we describe the optimal multi-version code for ν = 2 versions from the perspective of the storage cost log₂ q/ log₂ M. In particular, we show that for ν = 2, the optimal multi-version code has a storage cost of 2/c+1 when c is odd and 2(c+1)/c(c+2) when c is even. We also present achievable code constructions for arbitrary values of the parameter ν.