[mnet-devel] analytical solution to the FEC reliability problem

[Kyle Hasselbacher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Tue, Feb 25, 2003 at 06:08:02AM -0500, Zooko wrote:
>
>> I made graphs.  Find them here:
>
>Thanks Kyle!
>
>How did you calculate these?

I read your mail about five times with Excel open.  I think I made a change
to something (like, a value was (X-Y) instead of (Y-X)).  Anyway, I came up
with something that did what looked right.  I made the final graphics by
cropping screen captures (you can see some of the spreadsheet "behind" the
graph because I wanted to include the values I entered in the output).  As
I'm looking at it this morning, I'm questioning whether it's right.  I
plugged in "1 of 2" and expected a straight line, but it's more of a
parabola.

I have a 30K spreadsheet that will give you "chance of winning" for any "X
of Y" and P(S) "probability of retrieving one share".  From that, I got a
21M spreadsheet (which compresses nicely to a 3.8M ZIP) that does the
graphs.  It's big because it has a 250x1000 array in it that's used to
compute the 1000 values that the graph actually uses.  It takes about a
second to recompute on my 1.7GHz laptop.  Someone who knows Excel better
than I do could probably make it faster and smaller.

If there's interest, I can clean them a little and put them up next to the
graphs where people can get them.

>Could you add some more for me?  I'm interested in cases where M = 4*K.
>
>(e.g.  128 of 32, 64 of 16, 32 of 8, 24 of 6, and 8 of 2)

They're up, have a look.

In general, my observations are pretty simple (maybe even obvious):

- - Fewer shares means a flatter curve with less space "way close to 1" and
  "way close to 0".
- - Fewer shares needed to win means the curve is more to the left (low
  probabilities of success).  That is, they withstand failure better.

So:  If you know your network is fairly reliable, it's good to go with lots
of shares.  Lots of shares only becomes a problem if your reliability falls
below a certain point.  When it does, your chance of winning falls fast.
Fewer shares means less chance of winning in general, but there's not such
a tiny reliability region where chance of winning just goes all to hell.

It seems as if "area under the curve" should be a meaningful number, but I
haven't figured out how to describe its meaning.
- -- 
Kyle Hasselbacher | "It's easier to port a shell than a shell script."
kyle at toehold.com  |                         -- Larry Wall
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+W6fe10sofiqUxIQRArQqAKCLIQXsCQHW4iJERZxfOyrDpwbz4QCg2oVQ
XvUBWxNQ4Aylv1sDAQdvE+4=
=YXYr
-----END PGP SIGNATURE-----


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel