Derandomized construction of combinatorial batch codes

DOI10.1007/978-3-319-22177-9_21MaRDI QIDQ2947886zbMATH OpenOpenAlexFDO

Publication date 29 September 2015

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

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

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Combinatorial codes (94B25) Other types of codes (94B60)

Abstract: Combinatorial Batch Codes (CBCs), replication-based variant of Batch Codes introduced by Ishai et al. in STOC 2004, abstracts the following data distribution problem:

n

data items are to be replicated among

m

servers in such a way that any

k

of the

n

data items can be retrieved by reading at most one item from each server with the total amount of storage over

m

servers restricted to

N

. Given parameters

m, c,

and

k

, where

c

and

k

are constants, one of the challenging problems is to construct

c

-uniform CBCs (CBCs where each data item is replicated among exactly

c

servers) which maximizes the value of

n

. In this work, we present explicit construction of

c

-uniform CBCs with

O m e g a (m^{c - 1 + 1 o v e r k})

data items. The construction has the property that the servers are almost regular, i.e., number of data items stored in each server is in the range

[n c o v e r m - s q r t n o v e r 2 l n (4 m), n c o v e r m + s q r t n o v e r 2 l n (4 m)]

. The construction is obtained through better analysis and derandomization of the randomized construction presented by Ishai et al. Analysis reveals almost regularity of the servers, an aspect that so far has not been addressed in the literature. The derandomization leads to explicit construction for a wide range of values of

c

(for given

m

and

k

) where no other explicit construction with similar parameters, i.e., with

n = O m e g a (m^{c - 1 + 1 o v e r k})

, is known. Finally, we discuss possibility of parallel derandomization of the construction.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Derandomized construction of combinatorial batch codes

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