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.


  • $\begingroup$ Where is the question here? Please see mathoverflow.net/faq and mathoverflow.net/howtoask This question may be more suited to math.stackexchange.com $\endgroup$ – David Roberts Aug 9 '11 at 7:01
  • $\begingroup$ 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? I have posted this problem to math.stackexchange.com also. Thanks $\endgroup$ – aaaaaa Aug 14 '11 at 14:09
  • 1
    $\begingroup$ @David: This was asked at math.stackexchange as well. I refer the interested reader to the discussion in loc.cit. for a `better' problem description. I know nothing about convex optimization, but it does appear to me to be quite the wrong methodology. Prasenjit, if we set as our target that losing one box never causes data loss (otherwise, what's the point?), then what is wrong with the greedy algorithm: keep adding content to a box until the matrix describing what's outside that box fails to have a full rank. Rinse. Repeat. Randomize order, redo? $\endgroup$ – Jyrki Lahtonen Aug 16 '11 at 8:23

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.