We investigate in this work the problem of Erasure combinatorial batch codes, in which n files are stored on m servers so that every set of n - r servers allows a client to retrieve at most k distinct files by downloa...
详细信息
The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs), which are replication-based batchcodes. The MCBCs allow multiple ...
详细信息
The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs), which are replication-based batchcodes. The MCBCs allow multiple users to retrieve items in parallel in a distributed storage and a fundamental objective in this study is to determine the minimum total storage given certain requirements. We formulate linear programs so that the optimal solutions provide lower bounds on the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases. Furthermore, for some parameters, we showed that these lower bounds are either tight or asymptotically tight by constructing the corresponding codes.
Let n, r, k be positive integers such that 3 infinity. This problem is related to the forbidden hypergraph problem introduced by Brown, Erdos, and Sos and very recently discussed in the context of combinatorialbatch...
详细信息
Let n, r, k be positive integers such that 3 <= k < n and 2 <= r <= k - 1. Let m(n, r, k) denote the maximum number of edges an r-uniform hypergraph on n vertices can have under the condition that any collection of i edges spans at least i vertices for all 1 <= i <= k. We are interested in the asymptotic nature of m(n, r, k) for fixed r and k as n -> infinity. This problem is related to the forbidden hypergraph problem introduced by Brown, Erdos, and Sos and very recently discussed in the context of combinatorial batch codes (CBCs). In this short paper we obtain the following results. (i) Using a result due to Erdos we are able to show m(n, r, k) = o(n(r)) for 7 <= k, and 3 <= r <= k - 1 - inverted right perpendicularlog kinverted left perpendicular. This result is best possible with respect to the upper bound on r as we subsequently show through explicit construction that for 6 <= k, and k - inverted right perpendicularlog kinverted left perpendicular <= r <= k - 1, m(n, r, k) = Theta(n(r)). This explicit construction improves on the non-constructive general lower bound obtained by Brown, Erclos, and Sos for the considered parameter values. (ii) For 2-uniform CBCs we obtain the following results. (a) We provide exact value of m(n, 2, 5) for n >= 5. (b) Using a result of Lazebnik et al. regarding maximum size of graphs with large girth, we improve the existing lower bound on m(n, 2, k) (Omega(n(k+1/k-1))) for all k >= 8 and infinitely many values of n. (c) We show m(n, 2, k) = O(n(1+1/left perpendiculark/4right perpendicular)) by using a result due to Bondy and Simonovits, and also show m(n, 2, k) = Theta(n(3/2)) for k = 6, 7, 8 by using a result of Kovari, Sos, and Turan. (C) 2013 Elsevier B.V. All rights reserved.
A combinatorialbatch code has strong practical motivation in the distributed storage and retrieval of data in a *** this survey,we give a brief introduction to the combinatorial batch codes and some progress.
A combinatorialbatch code has strong practical motivation in the distributed storage and retrieval of data in a *** this survey,we give a brief introduction to the combinatorial batch codes and some progress.
The main purpose of this paper is to construct pliable fractional repetition (FR) codes that are locally recoverable for distributed storage systems (DSSs). FR codes are integral in constructing a class of distributed...
详细信息
The main purpose of this paper is to construct pliable fractional repetition (FR) codes that are locally recoverable for distributed storage systems (DSSs). FR codes are integral in constructing a class of distributed storage codes with exact repair by transfer. Pliable FR codes are a new type of FR codes in which both the per-node storage and repetition degree can easily be adjusted simultaneously;thus, pliable FR codes are vital for DSSs in which parameters can dynamically change over time. However, the constructions of pliable FR codes with repair locality remain unknown. In addition, the tradeoffs between the code minimum distance of an FR code and its repair locality are not fully understood. To address these problems, this paper first presents general results regarding FR codes. Subsequently, this paper presents an improved Singleton-like bound for locally recoverable FR codes under an additional requirement that each node must be part of a local structure that, upon failure, allows it to be exactly recovered by a simple download process. Moreover, this paper proposes a construction of locally recoverable FR codes that can achieve the proposed Singleton-like bound;this construction is based on bipartite graphs with a given girth. In particular, this paper also proposes a general bipartite-graph-based approach to constructing optimal pliable FR codes with and without repair localities;in this approach, a new family of bipartite graphs, called matching-feasible graphs, is introduced. Finally, this paper proposes the explicit constructions of optimal pliable FR codes by using a family of matching-feasible graphs with arbitrary large girth. Notably, in addition to attaining a Singleton-like bound for FR codes, the explicit pliable FR codes are optimal locally recoverable FR codes from two perspectives of repair locality. The explicit pliable FR codes can also be used as FR batchcodes to provide load balancing in DSSs.
Fractional repetition (FR) codes is a family of codes for distributed storage systems (DSSs) that allow for uncoded exact repairs having the minimum repair bandwidth. However, in contrast to minimum bandwidth regenera...
详细信息
Fractional repetition (FR) codes is a family of codes for distributed storage systems (DSSs) that allow for uncoded exact repairs having the minimum repair bandwidth. However, in contrast to minimum bandwidth regenerating (MBR) codes, where an arbitrary set of a certain size of available nodes is used for a node repair, the repairs with FR codes are table based. This usually allows to store more data compared with MBR codes. In this paper, we consider bounds on the FR capacity, which is the maximum amount of data that can be stored using an FR code. Optimal FR codes which attain these bounds are presented. The constructions of these FR codes are based on combinatorial designs and on families of regular and biregular graphs. These constructions of FR codes for given parameters raise some interesting questions in graph theory. These questions and some of their solutions are discussed in this paper. In addition, based on a connection between FR codes and batchcodes, we propose a new family of codes for DSS, namely, FR batchcodes, which have the properties of batchcodes and FR codes simultaneously. These are the first codes for DSS which allow for uncoded efficient exact repairs and load balancing which can be performed by several users in parallel. Other concepts related to FR codes are also discussed.
暂无评论