On Tuesday 31 March 2009 16:19:59 Gregory Maxwell wrote: > On Tue, Mar 31, 2009 at 10:59 AM, Matthew Toseland > <[email protected]> wrote: > > My understanding is the blocks available is no longer random, right? We need > > to be able to fetch random blocks, or at least whatever strategy we adopt > > needs to be able to provide the same probability of any given block being > > selected, when averaged over many fetches, so that some blocks do not fall > > out more quickly than other blocks. This is a problem with LDPC, correct? > > >From your perspective block LDPC should work just like the RS code does: > > The publisher encodes N blocks into M blocks and submits them into the network. > The client fetches some random subset of M, as soon as he has ~N of the M he > can reconstruct the original file. > > So no block is special. > > In the RS case N is always sufficient. For block LDPC you may need someplace > between N and N+ε of the blocks; the page I linked to links to a paper with > calculations about the size of ε. > > The advantage being that RS is slow and becomes much slower as M increases > and you're forced to use wider arithmetic. This means that practically > most applications > must break large files up and code in sub-groups, so rather than being > able to recover > using any N from the entire file, you must have X blocks from > subgroup1, X blocks from > subgroup2.. etc. > > If the important limit in freenet is I/O then this might all be moot. The block > LDPC should be basically neutral I/O wise vs RS, so the only advantage would be > being able to have longer correction windows (whole file) which would improve > reliability. Since the transmission units in freenet are large (as opposed to > 1400 byte IP datagrams) then perhaps there isn't much gain there. > > In any case, I just thought it would be worth your consideration.
I thought LDPC did XORs of different data blocks? If so, can't we do the decode progressively without having to read and write all the blocks at once stripe-wise, which is what causes the massive number of seeks?
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
