MaxMinSum Steiner systems for access balancing in distributed storage

DOI10.1137/17M1143964MaRDI QIDQ3174717zbMATH OpenOpenAlexWikidataFDO

Authors Hoang Dau, Olgica Milenkovic

Publication date 18 July 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.04986

zbMATH Keywords

Steiner triple systemsblock designsdistributed storagefractional repetition codesaccess balanceBose/Skolem constructions

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Applications of design theory to circuits and networks (94C30) Triple systems (05B07)

Abstract: Many code families such as low-density parity-check codes, fractional repetition codes, batch codes and private information retrieval codes with low storage overhead rely on the use of combinatorial block designs or derivatives thereof. In the context of distributed storage applications, one is often faced with system design issues that impose additional constraints on the coding schemes, and therefore on the underlying block designs. Here, we address one such problem, pertaining to server access frequency balancing, by introducing a new form of Steiner systems, termed MaxMinSum Steiner systems. MaxMinSum Steiner systems are characterized by the property that the minimum value of the sum of points (elements) within a block is maximized, or that the minimum sum of block indices containing some fixed point is maximized. We show that proper relabelings of points in the Bose and Skolem constructions for Steiner triple systems lead to optimal MaxMin values for the sums of interest; for the duals of the designs, we exhibit block labelings that are within a 3/4 multiplicative factor from the optimum.

Recommendations

• Access balancing in storage systems by labeling partial Steiner systems
• Kirkman systems that attain the upper bound on the minimum block sum, for access balancing in distributed storage
• Optimal combinatorial batch codes based on block designs
• Optimal fractional repetition codes based on graphs and designs
• Well-balanced designs for data placement

Cites work

• scientific article; zbMATH DE number 1314686 (Why is no real title available?)
• scientific article; zbMATH DE number 1096962 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• A Note on Steiner Triple Systems.
• Combinatorial Constructions of Low-Density Parity-Check Codes for Iterative Decoding
• Combinatorial Designs
• Distributed Storage Allocations
• Network Coding for Distributed Storage Systems
• On Quadruple Systems
• Optimal combinatorial batch codes based on block designs
• Optimal fractional repetition codes based on graphs and designs
• Some Remarks on the Triple Systems of Steiner.

Cited in

(12)

• On the maximum double independence number of Steiner triple systems
• Well-balanced designs for data placement
• Egalitarian Steiner quadruple systems of doubly even order
• Egalitarian Steiner triple systems for data popularity
• Asymptotic existence of egalitarian Steiner 2-designs
• Resolutions for an infinite family of Bose triple systems
• Egalitarian edge orderings of complete graphs
• Optimal fractional repetition codes based on graphs and designs
• Access balancing in storage systems by labeling partial Steiner systems
• Kirkman systems that attain the upper bound on the minimum block sum, for access balancing in distributed storage
• Construction of extended Steiner systems for information retrieval
• The spectrum of resolvable Bose triple systems

This page was built for publication: MaxMinSum Steiner systems for access balancing in distributed storage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174717)