Design cost versus access cost trade-off in distributed storage systems: A combinatorial approach

Seyed Rasoul Etesami, Mohammad Ali Maddah-Ali

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


Motivated by a class of resource allocation problems in cloud computing and storage systems, and aiming to capture the trade-off between design (implementation or hardware) cost and access cost, we introduce and study a new class of combinatorial problems. To be more specific, we consider a distributed storage system, with N files and K isolated memory units, where each memory has space to store M files, for some integers N, K, and KM ≥ N. At each time, a client asks for an arbitrary subset of T files, for some integer T ≥ M, and would like to read these T files by accessing the minimum number of memories. The objective in this paper is to characterize the fundamental trade-off between K, the number of memory units, and L, the number of memories that the client has to access in order to recover its requested T files. Other scenarios such as minimizing energy in server farms, or minimizing seek time in disk can also be formulated within the same underlying combinatorial problem. Through some counting arguments, we show that the required number of memories K has to be at least L/e(N/eML)T/L. Moreover, we show that there exists a solution which guarantees that the reader can read any T files by accessing to L memories, with K ≤ 2 (Ne/M)?T/L?. In particular, we introduce a simple probabilistic approach to place the memories' content, which achieves approximately the same trade-off. Finally, we justify the analytic trade-off bounds derived in this paper through some simulation results.

Original languageEnglish (US)
Title of host publication2016 American Control Conference, ACC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781467386821
StatePublished - Jul 28 2016
Event2016 American Control Conference, ACC 2016 - Boston, United States
Duration: Jul 6 2016Jul 8 2016

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Other2016 American Control Conference, ACC 2016
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Design cost versus access cost trade-off in distributed storage systems: A combinatorial approach'. Together they form a unique fingerprint.

Cite this