[darcs-users] Digital Fountain Codes for Patch Distribution

Tom Hawkins tomahawkins at gmail.com
Wed Nov 19 03:49:37 UTC 2008


We use darcs at work; and it works great.  The one exception is it's
slow.  We are still on 1.0.9 due to cygwin support, so maybe things
have greatly improved.  But in case they haven't, I'm wondering if
anyone has considered using digital fountain codes as a means to
communicate patches between repositories?  Fountain codes are a
forward error correction code designed to handle erasure channels.
They have the unique property of being an on-line code, which means
anyone that has complete, or partial information, can broadcast usable
information because the packets are generated at random, on the fly.

Translated to darcs, this means a repository could pull patches from
other repositoires in parallel, without needed to synchronize the
sources repositories.  The repo doing the pulling would simple create
a pipe to source repos A, B, and C; then A, B, and C would then start
streaming randomly generated packets of patch information; and once
the receiving repo collected enough information to reconstruct the
patches, it's done.

The performance of fountain codes is pretty good.  One would think
such a method would have a lot of redundent information.  But it turns
out the receiver only needs to receive about 5% more data than the
size of the original message.

And the dual of distributed downloading is unsynchronized
multicasting, which fountain codes can handle as well.

Just a thought.  Many thanks for such a great tool!


More information about the darcs-users mailing list