MaxMinSum Steiner systems for access balancing in distributed storage

DOI10.1137/17M1143964zbMATH Open1391.05053arXiv1708.04986OpenAlexW2745445621WikidataQ129516563 ScholiaQ129516563MaRDI QIDQ3174717FDOQ3174717

Authors: Hoang Dau, Olgica Milenkovic 

Publication date: 18 July 2018

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

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.

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

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

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)

Cites Work

• Combinatorial Designs
• On Quadruple Systems
• Network Coding for Distributed Storage Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Remarks on the Triple Systems of Steiner.
• Distributed Storage Allocations
• Combinatorial Constructions of Low-Density Parity-Check Codes for Iterative Decoding
• A Note on Steiner Triple Systems.
• Optimal combinatorial batch codes based on block designs
• Optimal Fractional Repetition Codes Based on Graphs and Designs

Cited In (9)

• On the maximum double independence number of Steiner triple systems
• 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
• Access balancing in storage systems by labeling partial Steiner systems
• 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)