Re: Triple parity and beyond

[Ric Wheeler <rwheeler@redhat.com>]

On 11/19/2013 12:28 PM, Andrea Mazzoleni wrote:
> Hi Peter,
>
> Yes, 251 disks for 6 parity.
>
> To build a NxM Cauchy matrix you need to pick N+M distinct values
> in the GF(2^8) and we have only 2^8 == 256 available.
> This means that for every row we add for an extra parity level, we
> have to remove one of the disk columns.
>
> Note that in true, I use an Extended Cauchy matrix that gives the
> first row of 1 for "free". This results in N+M <= 256+1.
> So, DISKS = 257 - PARITY -> 251 = 257 - 6
>
> A brief introduction of Cauchy and Extended Cauchy matrix can be found in:
>
> Vinocha, "On Generator Cauchy Matrices of GDRS/GTRS Codes", 2012
> http://www.m-hikari.com/ijcms/ijcms-2012/45-48-2012/brarIJCMS45-48-2012.pdf
> (just check the Introduction, the rest is not related)
>
> More details can be found in:
>
> Roth, "Introduction to Coding Theory", 2006
> http://carlossicoli.free.fr/R/Roth_R.-Introduction_to_coding_theory-Cambridge_University_Press%282006%29.pdf
> (search for "Extended Cauchy")
>
> Ciao,
> Andrea

Great work - we have waited a long time for this. Adding in Jim Plank who did 
some great talks and work in this area as well :)

Ric

>
> On Tue, Nov 19, 2013 at 12:25 AM, H. Peter Anvin <hpa@zytor.com> wrote:
>> On 11/18/2013 02:35 PM, Andrea Mazzoleni wrote:
>>> Hi Peter,
>>>
>>> The Cauchy matrix has the mathematical property to always have itself
>>> and all submatrices not singular. So, we are sure that we can always
>>> solve the equations to recover the data disks.
>>>
>>> Besides the mathematical proof, I've also inverted all the
>>> 377,342,351,231 possible submatrices for up to 6 parities and 251 data
>>> disks, and got an experimental confirmation of this.
>>>
>> Nice.
>>
>>> The only limit is coming from the GF(2^8). You have a maximum number
>>> of disk = 2^8 + 1 - number_of_parities. For example, with 6 parities,
>>> you can have no more of 251 data disks. Over this limit it's not
>>> possible to build a Cauchy matrix.
>>>
>> 251?  Not 255?
>>
>>> Note that instead with a Vandermonde matrix you don't have the
>>> guarantee to always have all the submatrices not singular. This is the
>>> reason because using power coefficients, before or late, it happens to
>>> have unsolvable equations.
>>>
>>> You can find the code that generate the Cauchy matrix with some
>>> explanation in the comments at (see the set_cauchy() function) :
>>>
>>> http://sourceforge.net/p/snapraid/code/ci/master/tree/mktables.c
>> OK, need to read up on the theoretical aspects of this, but it sounds
>> promising.
>>
>>          -hpa
>>
>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-raid" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html