Multi-version Coding with Side Information

Ramy E. Ali, Viveck R. Cadambe, Jaime Llorca, Antonia M. Tulino

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781538647806
StatePublished - Aug 15 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: Jun 17 2018Jun 22 2018

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2018 IEEE International Symposium on Information Theory, ISIT 2018
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Multi-version Coding with Side Information'. Together they form a unique fingerprint.

Cite this