Optimization problem related to parity check code

Question

I have n data blocks and k parity blocks distributed across m boxes. Each parity block is Ex-or of some data block (for ease of understanding we can assume each data/parity block as a single bit) and each data block is involved in some Ex-or operation to get some parity block. So, we have k parity equations as follows: P1= D11 Ex-or D12 Ex-or....... . . PK= Dk1 Ex-or Dk2 Ex-or....... 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. 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 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 where G=Σ g(i); i is from 1 to m

where g(i)=1 if failure of box i causes "dataloss" otherwise g(i)=0

Now the assignment of disk/pairty blocks across m boxes can be represented by a matix of dimension (n+k)Xm, 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<=n (for i>n), otherwise it is zero. So, the function G is a function of all those matrix entries and the constraints we have are : i) each matrix entry is either 0 or 1 ii) sum of the entries in a row is always 1 (i.e each data/parity block is present in exactly one box) iii) sum of the entries in each column is atleast 1 (i.e. no box is empty) iv) summation of all the matrix entries is n+k

I want to form a linear program or some optimization problem for which the solution methods are known. Basically writing the statement "if failure of box i causes "dataloss" in terms of matrix entries is creating problem.

Prasenjit

Answer 1

This is basically a retranslation of the problem into algebraic language. We are given an $n\times(n+k)$ matrix $A$ with entries in $GF(2)$ of the form $A=(I_n\mid B)$, where the matrix $B$ has no zero rows or columns (in practice it can probably be carefully designed, but the question is about finding a working general approach).

The problem at hand is to partition the columns of $A$ into at most $m$ subsets of size at most $b$ with the following property (so obviously $mb\ge n+k$): the removal of any single one of the subsets of columns in the partition leaves us a matrix $A'$ that is of full rank $n$.

The OP seems to be willing to relax the design goal somewhat and offers as an alternative goal to minimize the number of 'critical' partitions whose removal violates the rank criterion. This may be necessary for some combinations of parameters (and a bad value of $B$), so it is understandable, given that he seems to be looking for a general method. OTOH from the point of view of the probable application (if $m$ is 'large') one might also want to optimize the chanches that the removal of any two (or more) partitions of columns still leaves a full rank matrix, but that is a generalization of the original question.

My guess is that an accurate general algorithm may have prohibitively high complexity and offer a natural greedy algorithm of keeping assigning columns to partitions unless the rank condition is violated and hoping for the best (increasing $m$ on the fly if need be). Add reruns and a non-deterministic starting order to the mix.