TY - GEN
T1 - Multi-version Coding with Side Information
AU - Ali, Ramy E.
AU - Cadambe, Viveck R.
AU - Llorca, Jaime
AU - Tulino, Antonia M.
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/8/15
Y1 - 2018/8/15
N2 - In applications of storage systems to modern key-value stores, the stored data is highly dynamic due to frequent updates from the system write clients. The multi-version coding problem has been formulated to study the cost of storing dynamic data in asynchronous distributed storage systems. In this problem, previous work considered a completely decentralized system where a server is not aware of which versions of the data are received by the other servers. In this paper, we relax this assumption and study a system where a server may acquire side information of the versions propagated to some other servers. In particular, we study a storage system with n servers that store v totally ordered independent versions of a message. Each server receives a subset of these \nu versions that defines the state of that server. Assuming that the servers are distributed in a ring, a server is aware of which versions have been received by its h-hop neighbors. If the server is aware of the states of (n - 2) other servers, we show that this side information can result in a better storage cost as compared with the case where there is no side information. Through an information-theoretic converse, we identify scenarios where, even if the server is aware of the states of (n -3) /2 other servers, the side information may not help in improving the worst-case storage cost beyond the case where servers have no side information.
AB - In applications of storage systems to modern key-value stores, the stored data is highly dynamic due to frequent updates from the system write clients. The multi-version coding problem has been formulated to study the cost of storing dynamic data in asynchronous distributed storage systems. In this problem, previous work considered a completely decentralized system where a server is not aware of which versions of the data are received by the other servers. In this paper, we relax this assumption and study a system where a server may acquire side information of the versions propagated to some other servers. In particular, we study a storage system with n servers that store v totally ordered independent versions of a message. Each server receives a subset of these \nu versions that defines the state of that server. Assuming that the servers are distributed in a ring, a server is aware of which versions have been received by its h-hop neighbors. If the server is aware of the states of (n - 2) other servers, we show that this side information can result in a better storage cost as compared with the case where there is no side information. Through an information-theoretic converse, we identify scenarios where, even if the server is aware of the states of (n -3) /2 other servers, the side information may not help in improving the worst-case storage cost beyond the case where servers have no side information.
UR - http://www.scopus.com/inward/record.url?scp=85052468456&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052468456&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2018.8437658
DO - 10.1109/ISIT.2018.8437658
M3 - Conference contribution
AN - SCOPUS:85052468456
SN - 9781538647806
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1934
EP - 1938
BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018
Y2 - 17 June 2018 through 22 June 2018
ER -