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