Checking of Reed-Solomon Vandermonde parameter combinations

Checking of Reed-Solomon Vandermonde parameter combinations

[Loic Dachary]

[-- Attachment #1: Type: text/plain, Size: 1037 bytes --]

Hi Andreas,

There are some combinations of K/M parameters for which Reed-Solomon Vandermonde may not be able to recover from the loss of M chunks. Reed-Solomon Cauchy does not suffer from this problem. (I'm paraphrasing a conversation we had in private, feel free to correct me if I'm wrong).

In the context of Ceph we are interested in a limited range of parameters so I ran a test with:

https://github.com/ceph/ceph/blob/master/src/test/erasure-code/ceph_erasure_code_benchmark.cc#L40

for k in $(seq 2 50) ; do for m in $(seq 1 $k) ; do echo -n "k=$k m=$m " ; ./ceph_erasure_code_benchmark      --plugin jerasure      --parameter directory=.libs      --parameter technique=reed_sol_van      --parameter k=$k      --parameter m=$m --erasures $m      --iterations 1 --workload decode ; done ; done

and it does not throw an error. It basically take a range of parameters K=2,M=2 up to K=50,M=50 and decode with M erasures for each of them. Should some of them fail ?

Cheers
-- 
Loïc Dachary, Artisan Logiciel Libre


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 263 bytes --]

RE: Checking of Reed-Solomon Vandermonde parameter combinations

[Andreas Joachim Peters]

Hi Loic, 
as much as I understood for now it should not happen in Jerasure, but it will happen with the default Vandermonde matrix in the Intel library. The reason is the way these matrices are constructed.

But to verify this you have to make millions of iterations not only 1 because for large (k,m) there many failure scenario (chunk combinations) to test.

Cheers Andreas.

________________________________________
From: Loic Dachary [loic@dachary.org]
Sent: 03 July 2014 12:22
To: Andreas Joachim Peters
Cc: Ceph Development
Subject: Checking of Reed-Solomon Vandermonde parameter combinations

Hi Andreas,

There are some combinations of K/M parameters for which Reed-Solomon Vandermonde may not be able to recover from the loss of M chunks. Reed-Solomon Cauchy does not suffer from this problem. (I'm paraphrasing a conversation we had in private, feel free to correct me if I'm wrong).

In the context of Ceph we are interested in a limited range of parameters so I ran a test with:

https://github.com/ceph/ceph/blob/master/src/test/erasure-code/ceph_erasure_code_benchmark.cc#L40

for k in $(seq 2 50) ; do for m in $(seq 1 $k) ; do echo -n "k=$k m=$m " ; ./ceph_erasure_code_benchmark      --plugin jerasure      --parameter directory=.libs      --parameter technique=reed_sol_van      --parameter k=$k      --parameter m=$m --erasures $m      --iterations 1 --workload decode ; done ; done

and it does not throw an error. It basically take a range of parameters K=2,M=2 up to K=50,M=50 and decode with M erasures for each of them. Should some of them fail ?

Cheers
--
Loïc Dachary, Artisan Logiciel Libre

--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Checking of Reed-Solomon Vandermonde parameter combinations

[Loic Dachary]

[-- Attachment #1: Type: text/plain, Size: 1862 bytes --]

Thanks for the clarification, we're good then :-)

On 03/07/2014 12:27, Andreas Joachim Peters wrote:
> Hi Loic, 
> as much as I understood for now it should not happen in Jerasure, but it will happen with the default Vandermonde matrix in the Intel library. The reason is the way these matrices are constructed.
> 
> But to verify this you have to make millions of iterations not only 1 because for large (k,m) there many failure scenario (chunk combinations) to test.
> 
> Cheers Andreas.
> 
> ________________________________________
> From: Loic Dachary [loic@dachary.org]
> Sent: 03 July 2014 12:22
> To: Andreas Joachim Peters
> Cc: Ceph Development
> Subject: Checking of Reed-Solomon Vandermonde parameter combinations
> 
> Hi Andreas,
> 
> There are some combinations of K/M parameters for which Reed-Solomon Vandermonde may not be able to recover from the loss of M chunks. Reed-Solomon Cauchy does not suffer from this problem. (I'm paraphrasing a conversation we had in private, feel free to correct me if I'm wrong).
> 
> In the context of Ceph we are interested in a limited range of parameters so I ran a test with:
> 
> https://github.com/ceph/ceph/blob/master/src/test/erasure-code/ceph_erasure_code_benchmark.cc#L40
> 
> for k in $(seq 2 50) ; do for m in $(seq 1 $k) ; do echo -n "k=$k m=$m " ; ./ceph_erasure_code_benchmark      --plugin jerasure      --parameter directory=.libs      --parameter technique=reed_sol_van      --parameter k=$k      --parameter m=$m --erasures $m      --iterations 1 --workload decode ; done ; done
> 
> and it does not throw an error. It basically take a range of parameters K=2,M=2 up to K=50,M=50 and decode with M erasures for each of them. Should some of them fail ?
> 
> Cheers
> --
> Loïc Dachary, Artisan Logiciel Libre
> 

-- 
Loïc Dachary, Artisan Logiciel Libre


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 263 bytes --]