Optimization problem for a parity-check code

I have $n$ data blocks and $k$ parity blocks distributed across $m$ boxes where each box can contain atmost $b$ blocks. Each parity block is Ex-or of some data blocks (for ease of understanding we can assume each data/parity block as a single bit) and each data block is involved in atleast one Ex-or operation to get some parity block. Each data block can be involved in more than one parity block operation, infact will be as that will increase the fault tolerance of the code. So, we have $k$ parity equations as follows:

\begin{aligned} P_1 &= D_{11} \oplus D_{12} \oplus \cdots \\ \;\vdots \\ P_k &= D_{k1} \oplus D_{k2} \oplus \cdots \end{aligned}

Now if some data or parity block fails and we cannot recover the lost data blocks from the non-failed data/parity blocks we call this situation a "dataloss" situation. Now, I will give a simple example to explain this. Assume that we have $4$ data blocks and $3$ parity blocks where the parity equations are as follows: \begin{aligned} P_1 &= D_{1} \oplus D_{3} \oplus D_{4}\ \\ P_2 &= D_{1} \oplus D_{2} \oplus D_{3}\ \\ P_3 &= D_{2} \oplus D_{3} \oplus D_{4} \end{aligned}

We represent them by a matrix called generator matrix which is a $4$x$7$ matrix which is as follows:

$$G=\left(\begin{array}{ccccccc} 1&0&0&0&1&1&0\\ 0&1&0&0&0&1&1\\ 0&0&1&0&1&1&1\\ 0&0&0&1&1&0&1 \end{array}\right)$$

Now, suppose $D1$,$D2$,$D3$ fails and we want to check whether that causes dataloss. So, we remove the columns corresponding to $D1$,$D2$,$D3$ from G and call the matrix we get "recovery matrix" which is

$$G'=\left(\begin{array}{cccc} 0&1&1&0\\ 0&0&1&1\\ 0&1&1&1\\ 1&1&0&1 \end{array}\right)$$ here. Now, we check the rank of $G'$. If this is less than $n$ then we have $dataloss$, otherwise not. Here $rank$(G')=4 and $n$=4 and we don't have any $dataloss$. Basically, if we Ex-or $P1$,$P2$,$P3$ then we can recover $D3$, from that we can recover $D1$,$D2$.

A data/parity block fails if and only if the box containing it fails and if a box fails then all the data and parity blocks inside it fails. Now we want to formulate the following optimization problem:

Given $n$, $k$, $m$ and the $k$ parity equations (we are not allowed to choose which data blocks are xor-ed to form a check block, we are given an erasure code system) we want an assignment of the disk and parity blocks across $m$ boxes such that we can minimise the number cases where a box failure causes "dataloss"; i.e I want to minimise the function $G=\sum_{i=0}^m\;g(i)$, where

$$g(i) = \begin{cases} 1 & \text{if failure of box }i\text{ causes "dataloss"} \\ 0 & \text{otherwise} \end{cases}$$

Now the assignment of disk/parity blocks across $m$ boxes can be represented by a matrix of dimension $(n+k) \times m$, lets call it $B$. The $(i,j)$-th entry of the matrix is $1$ if the $j$-th box contains $i$-th data block ($(i-n)$-th parity block) for $i \le n$ (for $i>n$), otherwise it is $0$. So, the function $G$ is a function of all those matrix entries and the constraints we have are:

1. each matrix entry is either 0 or 1
2. sum of the entries in a row is always 1 (i.e each data/parity block is present in exactly one box)
3. sum of the entries in each column is at least 1 (i.e. no box is empty)
4. summation of all the matrix entries is $n+k$

Now, the function $G$ is coming as a non-linear function of the matrix entries. Also the domain set of $G$ is set of all $n$-tuples where elements of a tuple are 0 or 1. So, the domain set is not a convex set, so convex optimization techniques can't be applied here. How to solve this optimization problem?

If I refine problem like this: How much of the $n+k$ blocks can be covered using m subsets each of size atmost b then I think it is possible to formulate it as a maximum independent set problem. We will form a graph of n+k vertices where each vertex corresponds to one block(data/parity) but the definition of edges is not clear to me (this is the main problem I am trying to solve). Then the maximum independent set of this graph will give us the maximum subset (of the n+k columns) that can be covered.

Somehow I feel that the problem is NP-Complete.

Hope I have described the problem clearly.

======

Edit (comment from Jyrki Lahtonen): This was also posted at MO. I try to redirect eventual interested MO-posters here, because at the moment I think we have a better description of the question here.

-
In "Each parity block is Ex-or of some data block", I think you mean "data blocks" in the plural? The singular doesn't seem consistent with what follows. Also, in "each data block is involved in some Ex-or operation to get some parity block", is the implication that each data block is involved in exactly one parity block operation? –  joriki Aug 14 '11 at 14:32
I think that you should tell a little bit more: How many blocks fit into a single box? Are we allowed to try to be clever in choosing which data blocks are XORed to form a check block? (that has an effect on the sets of blocks that we need to have in order to recover a data block) If I understood it correctly, you are optimizing a code for distributed storage. Then your luck is in, because P. Vijay Kumar from IISc, Bangalore, is one of the leading experts of the field (AFAIK). You may also benefit from a study of ideas underlying fountain codes? –  Jyrki Lahtonen Aug 14 '11 at 15:20
@all Thanks for yor reply. I forgot to mention one constraint that "each box can contain at most b blocks". –  aaaaaa Aug 14 '11 at 16:07
@ joriki: each data block can be involved in more than one parity block operation, infact will be as that will increase the fault tolerance of the code –  aaaaaa Aug 14 '11 at 16:28
@Jyrki: no we are not allowed to choose which data blocks are xor-ed to form a check block. We are given an erasure code system and we want to optimize the configuration for that code. So, the code is fixed and we want to find which configuration will give me maximum reliability rather than what you are saying. –  aaaaaa Aug 14 '11 at 16:29

Sorry to add another answer, but I feel that my first answer contains relevant clarifications to the problem definition, so I think that keeping it separate is justified. Also that other answer is already so long that editing it is painfully slow given that the preview renderer is eating all the cycles.

IMHO the only worthy goal here is that it never happens that the loss of a single box results in data loss. If you cannot tolerate the loss of a single box, you need to engineer that particular box to be fool-proof, and therefore you might as well keep all the data in there. Ok, you may give some weight to partial data recovery, but you didn't ask for it, and then we definitely need to know more about the erasure recovery code.

Here's my first suggestion. The good old greedy algorithm. First randomize the order of the $n+k$ data and check blocks (not necessary, but I want to add a non-deterministic element), so we have blocks $b_1,b_2,\ldots,b_{n+k}$. The algorithm will assign each and every one of these to one of the boxes as follows.

1. Initialize $j=1$. Initialize the list of unassigned blocks to the list $b_1,\ldots,b_{n+k}$.
2. Initialize box $\#j$ to be empty. Initialize a pointer $p$ point to the first entry in the list of unassigned blocks.
3. Check whether adding the block pointed at by $p$ to box $\#j$ violates the rank condition or not (gaussian elimination does this in polynomial time). If it does not, then assign that block to box $\#j$, advance the pointer $p$ and remove that block from the list of unassigned blocks.
4. If box $\#j$ is full, or the pointer $p$ went beyond the end of the list, then go to step 5. Otherwise go to step 3.
5. If you have assigned all the data blocks exit with success. Otherwise increment $j$. If you are out of boxes, exit with failure. Otherwise go to step 2.

If one random order doesn't work, try a different one.

It seems to me that the complexity of this is polynomial in $n+k$. It exits successfully, if it finds an assignment of the desired type. You may also want to leave the number of boxes open, in which case the algorithm always succeeds, but should also output the number of boxes it needed.

But I would guess that you (or somebody in your team) have already tried this. What's wrong with it? No proof? Would need to have a (heuristically) justifiable reason to prefer one random order over another?

-
It will take some time for me to comment –  aaaaaa Aug 16 '11 at 11:52
@Prasenjit: You don't need to try all the $(n+k)!$ orderings. If there is a partition of the columns into $m$ groups of $b$ each, then this algorithm will find the partition for at least $(m!)(b!)^m$ different orderings (probably a lot more given that the algorithm will reject some columns) as we don't care about the order of the boxes nor about the order the columns are assigned into the boxes. –  Jyrki Lahtonen Aug 28 '11 at 14:47
@Prasenjit: But I agree that this is not a solution to your original question. The greedy algorithm has the air that: given $n$, $k$, $b$ and the erasure recovery code, minimize $m$. It doesn't solve that one either, but I would think that for a widish range of values the output would not be too far off the minimum $m$. But: no proof, no cigar :-( –  Jyrki Lahtonen Aug 28 '11 at 14:50

The OP has also posted this problem at StackOverflow and clarified it in Comments there.

The Question can be framed as a combinatorial one. Given a "universe" set $S$ of size $n$, consider a collection $A$ of subsets of $S$ consisting of the $n$ singleton subsets together with $k$ additional (distinct) subsets of size at least two. Thus $|A| = n+k$.

We are then asked to partition $A$ using at most $m$ parts and with parts of size at most $b$, where $mb \ge n+k$. The objective is to find such a partition in which as few of the parts as possible have a certain property, which Prasenjit refers to as "critical". This motivates the definition:

A subset $B$ of $A$ has property C iff the Boolean algebra generated by $A \backslash B$ is a proper subalgebra of $\mathscr{P}(S)$.

A little reflection should convince the reader that the point set condition above amounts to the criterion Prasenjit gives for the removal of columns from generator matrix $G$ resulting in a matrix of rank less than $n$.

Prasenjit's question is then: Considering all partitions of $A$ having at most $m$ parts of at most size $b$, what is the least possible number of parts having property C.

My suggestion is to first determine how much of $A$ can be covered by at most $m$ subsets $B$ of size at most $b$ not having property C. Since the condition of not having property C is closed under taking subsets, such a cover can always be refined to a partition with no parts having property C. If possible this would attain a minimum.

If not possible then at least one part having property C would be required.

Since all the $k$ non-singleton sets in $A$ form a subset not having property C, it is only a singleton set in $A$ that might be impossible to include in a "block" $B$ (subset of $A$ of size at most $b$) not having property C.

However the parameter $m$ might be specified so low that even though every set in $A$ is included in a "block" not having property C, it is nonetheless impossible to cover all $A$ with just $m$ such blocks. This would of course be the case if $m=1$, although it would then be clear that the minimum number of blocks with property C required is 1.

-
Are you talking of a polynomial algorithm for this problem or trying to prove that it is NP-Complete? What you have said above is pretty obvious as the problem to "first determine how much of A can be covered by at most m subsets B of size at most b not having property C" (as you have said) is the hard part of the problem and that's why I suspect it as an NP-Complete problem. –  aaaaaa Aug 27 '11 at 6:10
@Prasenjit: The main purpose was to bring over the clarifications from your post at StackOverflow. Secondarily the restatement of the problem in combinatorial terms vs. linear algebra seems to give some insight, as for example covers rather than partitions are the essential requirement. Also the difficulty lies in covering the singleton sets with blocks not having property C, in that the non-singleton sets can be so covered arbitrarily (subject only to the limitation of block size b). I'll add a note how many singleton sets can be covered by a single block not having property C. –  hardmath Aug 27 '11 at 14:56
@Prasenjit: I'd guess (if asked) that there is a polynomial time algorithm. In any case I'm trying to find an efficient algorithm for your problem. –  hardmath Aug 27 '11 at 15:01
I will be interested in knowing any polynomial time algorithm. Also the meaning of the statement "Since the condition of not having property C is closed under taking subsets, such a cover can always be refined to a partition with no parts having property C" is not clear to me. Can you elaborate your statements with some example. –  aaaaaa Aug 27 '11 at 17:27
I don't agree with your this statement "the non-singleton sets can be so covered arbitrarily (subject only to the limitation of block size b). We can't separate the process of covering the singleton sets and non-singleton sets because the property C depends on both singleton and non-singleton sets. If not clear I will give an example to demonstrate that. –  aaaaaa Aug 29 '11 at 14:55

This is too long to be comment, but I need to ask this to get/give a better idea of the problem setting. I cannot tell for sure, but based on my exposure to related problems I think it looks like the following: If the $n\times (n+k)$ binary matrix describing the presence of a data block in a data or a check block is $A$, then $A$ has $I_n$ block in the left (data block $D_i$ copied to its own block) and then a `random' (or carefully designed) $n\times k$ binary block $B$ telling us which data blocks are XORed to form that check block: one column per check block, so an entry '1' on a row $i$ and column $j$ of the matrix $B$ tells that data block $\#i$ is among those XORed to form check block $\#j$.

Now distributing these $n+k$ blocks of data into boxes amounts to partitioning the columns of the matrix $A$ into $m$ subsets. AFAICT data loss occurs, if and only if removal of the columns belonging to the box in question leaves us with a matrix $A'$ that is no longer of full rank $n$. This is because, if the matrix $A'$ were of full rank, we could select a subset of $n$ linearly independent columns. As they form an invertible matrix, data recovery could be done (by e.g. Gaussian elimination).

Is this what you have in mind? This seems to be closely related to erasure correction/recovery codes, and you may benefit from using that as a buzzword, when searching for more information.

Before we get serious, let me describe a toy example of the above. Let $$A=\left(\begin{array}{ccccccc} 1&0&0&0&1&1&0\\ 0&1&0&0&0&1&1\\ 0&0&1&0&1&1&1\\ 0&0&0&1&1&0&1 \end{array}\right)$$ be this matrix that some of you will recognize as the generaotr matrix of the the $[7,4,3]$ Hamming code. Here the last 3 columns tell that the first check block is constructed by XORring data blocks 1,3 and 4, the second check block by XORring data blocks 1,2,3 and the last check block by XORrin data blocks 2,3,4.

I claim that in this case using $m=3$ boxes allows us to always recover from the loss of any single box. Put data blocks 1,2 into the first box; data blocks 3,4 into the second box; and all the check blocks into the third box. If we lose the third box, then we obviously have all the data in tact. If we lose the first box, then we can recover data block #1 by XORring the first check block with data blocks 3 and 4, and similarly we can recover data block #2 by XORring the last check block with data blocks 3 and 4. Similarly if we lose the second box, then we can recover the missing data blocks 3 and 4 usigng the the saved check blocks and the saved data blocks 1 and 2.

Because this binary code has minimum Hamming distance 3, it can recover from any two erasures. Therefore I knew in advance that I woudl be able to recover the lost contents of either of the first two boxes.

Please comment. I realize that you may be looking for a different approach. May be one with simpler recovery schemes?

-
I've deleted my answer -- your interpretation makes a lot more sense. If this is what was intended, "each data block is involved in some Ex-or operation to get some parity block" should be edited to read "each data block is involved in the XOR operation of at least one parity block". Also the notation should be clarified to reflect that $D_{11}$ isn't the name of a parity block but a variable that takes data blocks as values and may take the same value as e.g. $D_{k1}$. –  joriki Aug 14 '11 at 16:22
@joriki: yes you are right, I will be careful when I will post here again next time –  aaaaaa Aug 14 '11 at 16:33
@joriki: I agree that the question was somewhat confusing. I am making educated guesses here, but I have a lot of exposure in this area, so that helps. Nothing wrong with your answer. It helped pinpoint weak points in the formulation of the problem. Probably need a few iterations to see what the question really is. –  Jyrki Lahtonen Aug 14 '11 at 16:37
@ Jyrki: you are right. There will be dataloss iff the recovery matrix has rank less than n. I used this and then got G as a non-linear function of matrix entries and not able to proceed after that. –  aaaaaa Aug 14 '11 at 16:38
@Prasenjit: Ok. I think I understand the question now. I will go off air soon, but if I think of something I will let you know. An understanding of the minimal words of the dual code may help, but may be not. –  Jyrki Lahtonen Aug 14 '11 at 16:49