Damn Cool Algorithms: Fountain Codes

http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes

by nl • 15 years ago

306 62 15 years ago

blog.notdot.net

cma• 15 years ago

heavily patented

epaulson• 15 years ago

Alas, digital fountains are tied up in patents, and people have been leery:

http://www.eecs.harvard.edu/~michaelm/postscripts/itw2004.pd...

michaelf• 15 years ago

I know there are lots of anti-patent folks on HN, but if anything deserves patent protection, digital fountains certainly do. This is useful, novel, and certainly non-obvious stuff. And really quite beautiful, IMHO.

Its always bothered me to read about inventors who discovered beautiful and amazing things, only to die penniless while powerful interests reaped all of the financial benefits. Hopefully the people who discovered these codes have been richly rewarded for their work.

wmf3• 15 years ago

While I don't begrudge Luby his patents on the specific codes he invented, IIRC he has claimed that his patents cover the entire class of all possible rateless codes, which is trollish behavior. One startup that I know of has gone out of business due to Luby.

JoshTriplett4• 15 years ago

> I know there are lots of anti-patent folks on HN, but if anything deserves patent protection, digital fountains certainly do.

I'd suggest that the usefulness of algorithms like fountain codes (and other innovative algorithms like RSA and many compression techniques) leads to the opposite conclusion: such algorithms prove so broadly useful that patents on them have even more of a negative effect than usual.

eldina• 15 years ago

This is useful, novel, and certainly non-obvious stuff.

So you would like to have had eg. any useful non-obvious algorithm or data structure which at some point in history was novel been patented ? Yikes.

throwaway64• 15 years ago

You seem to be operating from the premise the creator of an idea has some sort of intrinsic right to solely profit from ideas of his own "creation". There is no intrinsic right there, ideas are not physical property, we should not treat them like they are.

I put creation in quotes, because of an issue that nicely demonstrates how fundamentally different ideas are from physical property: consider the many scientific/mathematic discoveries[1] that were made in parallel around the world, with no communication between the parties, who gains the right to "own" these ideas, and why should they? Did not somebody else take exactly the same amount of effort and process to create the exact same idea? This even applies to very complex systems that are far from obvious, quite novel, and form the foundations of our modern world.

People need to get past the idea that somebody has a brilliant idea one day out of the blue, and the world is changed forever because of it. Every idea anyone has ever had owes almost everything to what proceeded it, and the environment it arose in, co-discovery/invention is very solid proof of that.

"If I have seen a little further it is by standing on the shoulders of Giants."

When you take the time to realize the very thing that propels us forward is the ability to build on existing ideas, you realize how patents and IP law in general are impeding, not encouraging.

[1] https://en.wikipedia.org/wiki/Calculus#Modern

https://en.wikipedia.org/wiki/Russels_paradox

https://en.wikipedia.org/wiki/Invention_of_the_telephone

https://en.wikipedia.org/wiki/List_of_scientific_priority_di...

https://en.wikipedia.org/wiki/Stigler%27s_law_of_eponymy

(there are several more, but i do not have the time just now to find them)

gambler• 15 years ago

I would challenge this by asking the following questions:

1. Is it non-obvious enough? 2. Would the patent realistically benefit the inventor? 3. Would the patent benefit the society at large?

1 - Physical devices often require lots of engineering work, prototyping, testing and refinement before they really work. Patents aim to protect your investment of money and time into all that stuff. This is not applicable to pure ideas. Once you thought of something like fountain codes, you instantly know they will work and you even know how. There is no investment to protect.

2 - Just because something is useful doesn't mean people will use it, even for free, and the act of patenting a generic algorithm will certainly drive most potential users away. Not because licensing costs money, but because it's a hassle and a liability.

3 - This was covered in many other posts here. I'll add one thing. The fact that it's just an idea (and a generic one that that) means other bright people who need that idea are likely to come up with it on their own. In that case a patent would be clearly counter-productive for the society. Why should the first 'inventor' of the algorithm has all the rights to it, while the second would have none?

invalidOrTaken• 15 years ago

Thanks for this post. Patented or not, this is damn cool.

beambot2• 15 years ago

Arg. I thought algorithms weren't supposed to be patentable. I know there are workarounds (like referring to the "algorithm" as a "system"). But it's frustrating nonetheless.

For the curious, Knuth wrote an interesting letter on the topic back in 1994: http://www.pluto.it/files/meeting1999/atti/no-patents/brevet...

cydonian_monk• 15 years ago

We had a patent officer visit our senior design class in engineering school and this question came up. We were all of the opinion that algorithms were purely mathematical expressions, as Dr. Knuth insists in the letter you cited. I don't recall the patent officer ever giving a precise answer on the subject, but I do recall considerable dancing as he attempted to explain why math isn't always math to a room full of engineers.

phzbOx• 15 years ago

Didn't know about that algorithm, pretty cool. Also, the way the author explained it made it a joy to read.. clear, simple examples, meaningful graphics. Can't wait to start reading the previous blog posts (About other cool algorithms).

derfclausen• 15 years ago

Luby had a startup named Digital Fountain in SF in the late 90's where they attempted to productize this, primarily for video streaming.

Looks like they were acquired by Qualcomm a few years back: http://www.qualcomm.com/solutions/broadcast-streaming/media-...

jws• 15 years ago

One wonders how it does rate limiting to avoid pointless resource consumption of faster, near links when the packets are going to be dumped by a slower, farther link.

In particular, if you intend to coexist fairly with TCPIP on an internet you might find your rate limiting code carries all the most of the work and timing issues of TCPIP anyway.

loeg• 15 years ago

This is not relevant to fountain codes.

baruch4• 15 years ago

The fountain code itself is not concerned with it, it's merely the coding layer. There needs to be a communications layer that takes care of that and the way it does that will need to consider co-habitating with TCP.

In the application I worked on we used multicast and implemented a form of multicast congestion control that was orthogonal to the coding but exploited the fact that we can send however much data as we wanted and the only thing that changed was the time it will take to complete the transfer. It worked beautifully with the coding and co-habitated nicely with TCP.

repiret• 15 years ago

Whats the advantage of Fountain Codes over more well known and deterministic forward error correction techniques like Reed-Soloman Codes?

The D.J.C.MacKay paper linked from the article lists applications in broadcast and data storage, but Reed-Soloman would work equally well in both those applications.

Hypothesis: With Reed-Soloman and friends, if you're unlucky and loose the /right/ n blocks, for small n, you can't recover your data. Is that n larger for LT? If I could maliciously corrupt your LT blocks, would I have to corrupt more with LT?

Hypothesis: If I randomly corrupt blocks with Reed-Soloman, does my likelihood of not being able to recover all my data drop faster than if I did so with LT?

Can someone say authoritatively?

jsyedidia2• 15 years ago

The advantage is you don't need to know the channel characteristics ahead of time. In particular, if you used a Reed-Solomon code, you'd use one designed for one particular erasure rate. But that code would be too weak for a channel with a higher erasure rate (it would fail to decode) and it would be too strong for a channel with a lower erasure rate (it would be wasteful and use too many parity bits). The advantage of fountain codes is that they work efficiently whatever the channel's erasure rate.

By the way, I've been talking about channels with an erasure rate (the Binary Erasure Channel) because fountain codes were originally invented in that context. But you can find in the literature papers on "Rateless codes for noisy channels" that show that the fountain codes also work fine for bit-flipping channels like the binary symmetric channel and the additive white Gaussian noise channel.

jacquesgt2• 15 years ago

Combine the adaptability of fountain codes with feedback, and you can vary the transmission rate as the channel quality changes. With applications like cellular radios, this lets you use just enough power to transmit messages intact, optimizing the power usage across a range of interference levels.

gwern• 15 years ago

> But that code would be too weak for a channel with a higher erasure rate (it would fail to decode) and it would be too strong for a channel with a lower erasure rate (it would be wasteful and use too many parity bits). The advantage of fountain codes is that they work efficiently whatever the channel's erasure rate.

So could we think of fountain codes as a kind of adaptive on-the-fly RS code in which one sends a block protected against one's best guess of the erasure rate and if the recipient fails to decode it one resends with a higher erasure rate, or if the recipient succeeds one sends the next block with a lower erasure rate?

jacquesgt2• 15 years ago

Reed-Solomon and similar codes correct for bit errors in a particular block by transmitting extra bits in each block. Fountain codes correct for missing blocks by transmitting extra blocks.

If you just used RS, the only way to overcome really long bursts of errors (thousands or millions of bits long) would be to either to request acknowledgements from the receivers and retransmit unacknowledged blocks. If acknowledgements weren't possible, you would need to transmit everything multiple times. And, if you had enough receivers, all missing random packets, you would end up retransmitting everything even if you had acknowledgements. By using fountain codes, you can transmit an extra few percent of blocks and still succeed in the face of long dropouts.

wmf3• 15 years ago

Reed-Solomon and similar codes correct for bit errors in a particular block by transmitting extra bits in each block.

That's one way to think of it, but more generally they correct symbol errors by transmitting extra symbols. In some cases a symbol is a bit, but if you want a packet erasure code you just define a symbol to be a packet (or a disk block or whatever). A practical example of this is par2.

wmf3• 15 years ago

Parity codes (of which fountains are a subset) are based on XOR, making them much faster than RS's Galois field arithmetic. Parity codes are generally less efficient than RS (you have to receive 5-10% extra data to recover), but the net performance is better due to faster decoding.

jsyedidia explained the benefits of ratelessness, so I won't repeat it.

Yrlec• 15 years ago

What you said is correct but just to be nit-picky: parity codes constitute Galois Field arithmetic as well. XOR is the addition operation of polynomials in GF(2^n).

tikhonj• 15 years ago

This sounds really similar to secret sharing[1]. While not doing exactly the same thing, a simple secret sharing algorithm is also interesting to read about now--it's a different algorithm chunking up and reassembling data in a similar way with different properties.

One difference is that with secret sharing unless you have enough chunks you do not have any information about the result. (That's why it's called secret sharing--you can share a secret with a bunch of people without any of them knowing it unless a minimum number get together.) The neat trick is that any subset of the chunks big enough will get you all of the information.

[1] http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

In fact, the algorithm (at a high level) is exceptionally simple: encode your data as the coefficients of a polynomial of degree n and transmit it as a bunch of points in the polynomial. You then need n+1 points to recover the polynomial, but which particular points you have does not matter.

What I love about this algorithm is that it is useful, nontrivial and can be explained in a single sentence (by a better writer than I :)).

zacharyvoase• 15 years ago

Another way of phrasing the same concept:

An infinite number of Euclidean planes can be drawn containing a single point, but you only need three of these—and it can be any three—to find the original point.

lurker14• 15 years ago

(if the original point is contained within a line that is also known. For example, if the original/desired point is on the x-axis)

evmar• 15 years ago

Gray on black text. :~(

To make the page readable, pull up the dev console and run `document.body.style.color='black'`

Lagged2Death2• 15 years ago

Or you could zap colors:

http://www.russellbeattie.com/blog/the-zap-colors-bookmarkle...

obtu• 15 years ago

That bookmarklet comes from squarefree (and looking at his about page, Russell Beatie should learn to credit other people): https://www.squarefree.com/bookmarklets/zap.html

karpathy• 15 years ago

It's somewhat intuitive, but I feel like there is some cool math or attempt at explanation behind this that was left out.

Why is this better than just broadcasting messages that always contain a single block? What do you gain by forming combinations? You still have an expectation of eventually getting all the information. I assume it just turns out to take longer on average because your expected gain in information is lower from single chunks once you already have many of them?

JoshTriplett4• 15 years ago

If you only broadcast messages that contain a single block, anyone who already has that block gets no value out of the message. On the other hand, if you broadcast messages generated via fountain codes, messages give you almost a full block worth of information on average.

If you assume the same network environment that the article does, namely one where no feedback occurs from the recipient to the sender, then if you miss a single block in the message, you'll have to wait for the sender to send that one block again. Since the sender has no information about what block you missed, you'll have to wait on average for half the blocks to get retransmitted, resulting in 50% overhead or more. It gets worse if you miss enough blocks that you have a non-trivial chance of missing those blocks again. (On top of that, some transmission mechanisms have properties that make particular data patterns particularly prone to loss, which makes it significantly more likely that you'll lose particular blocks repeatedly.)

With fountain codes and similar mechanisms, on the other hand, every message provides several chances to obtain the missing blocks, resulting in much less overhead.

baruch4• 15 years ago

It is a damn cool algorithm, I was introduced to it in a startup I worked in and we actually tried to make use of it. The algorithm as described has a problem to converge fast enough and we had to make some extra structure on top that made it converge very fast and in a very consistent way. We used it for multicast communications where feedback to the server is impractical and such codes are making it a very effective way to distribute the data.

jleader2• 15 years ago

Why does the described algorithm only decode transmitted blocks when the receiver has decoded all but one of the constituent blocks? For example, if the receiver has received the following 3 blocks:

  1. A ^ B ^ C
  2. A ^ B
  3. B ^ C

it can combine #1 and #2 to decode C, then combine C and #3 to decode B, then combine B and #2 to decode A.

The algorithm as described would in this situation cause the receiver to wait until it's received a single block, either A or B or C, before decoding anything. This strikes me as inefficient.

Edited to add: I think this is analogous to forward vs. backwards chaining: you can either start by combining single blocks with composite blocks to simplify them, or start by combining blocks whose component block lists differ by only a single block. Or you could apply both, which should get the greatest simplification with the smallest amount of input.

baruch4• 15 years ago

Normally one would use some distribution of the number of encoded source blocks in a block. So one would send 30% single blocks, 30% double blocks, 15% triple, and so on until you get some relatively small number of high order encoded blocks. This means that while you can find a solution the way you posted it is a rare case that you have no single block for decoding and since in any case you need to receive a bit over 100% of the blocks before you can decode anything there is no real reason to go to exquisite lengths to find the perfect solution when the trivial case will work 100% of the times (well 99.9999% if you cared to be accurate :-)

The algorithm is also not so much about computational efficiency, to check at any point if you can or cannot decode requires quite a bit of work anyhow. The main advantage of the algorithm is in its relative low complexity and high efficiency on the transmission line.

jleader2• 15 years ago

My point isn't about computational efficiency, but bandwidth efficiency (or alternatively, decoding the full message as early as possible). As I understand it, the Moore's law doubling time for bandwidth is longer than for CPU speed, suggesting that processing is getting cheaper relative to bandwidth, so using more CPU in order to have to send fewer blocks is probably a long-term win.

hadronzoo3• 15 years ago

RaptorQ codes, an efficient fountain code implementation, have a relative reception overhead of K+2 symbols with probability of 99.9999%. See: http://tools.ietf.org/html/draft-ietf-rmt-bb-fec-raptorq-06

foobarqux• 15 years ago

"Systematic code" is the term of art in coding. There are systematic fountain codes. The raptor code adopted by 3GPP is systematic.

kcl• 15 years ago

It wasn't immediately clear to me the ideal soliton distribution always summed to one. There is a simple proof by induction. I wrote it up here: http://kevinlawler.com/soliton

sown2• 15 years ago

Where do people keep these algorithms around? I've asked in the past about reference guides for stuff like this they throw Knuth's "Art of Computer Programming" which is a neat book but doesn't have esoteric and useful but hard to find stuff like this.

Where do I find stuff like this?!

nl2• 15 years ago

http://en.wikipedia.org/wiki/List_of_algorithms (seriously! Scan it, choose something that looks interesting and you'll have hours of fun ahead of you.)

iambot• 15 years ago

As much as it seems like common sense as that page would exist on Wikipedia, it had never occurred to me, Brilliant - Thank you.

sown2• 15 years ago

Thanks, but neither fountain nor rateless codes appear on that page. :(

sc00ter• 15 years ago

I don't pretend to understand most of it, but to my untrained eye, "Clever Algorithms" seems to be a phenomenal resource and available as a free PDF, or in print: http://www.cleveralgorithms.com/

Edit: Discussion here: http://news.ycombinator.com/item?id=2141542

silentbicycle• 15 years ago

Related, also recommended: _Essentials of Metaheuristics_ (http://cs.gmu.edu/~sean/book/metaheuristics/).

kareemsabri• 15 years ago

Isn't this network coding?

http://en.wikipedia.org/wiki/Network_coding http://research.microsoft.com/pubs/67246/tr-2004-80.pdf

calloc• 15 years ago

Seems the website has gone over quota. Shame, because the content is absolutely fantastic. Had it opened and had begun reading it on my computer at home.

Edootjuh• 15 years ago

Here's a mirror: http://blog.notdot.net.nyud.net/2012/01/Damn-Cool-Algorithms...

InnocentB• 15 years ago

NYUD gives me a 324 error (no bytes returned). This one worked for me: http://webcache.googleusercontent.com/search?q=cache:blog.no...

aidenn0• 15 years ago

This seems most useful for broadcast. You could just broadcast the fountain code of a file out as long as you have listening receivers; the only feedback needed would be "send to me" and "done"

sethbuzz• 15 years ago

Fountain codes look very interesting. There was a project at OLPC, I think written in Forth for OpenFirmware, that used something like fountain codes to reflash massive numbers of computers. It worked like this. Turn one XO-1 on in OFW mode, insert a USB with the disk image you wanted to be on all machines, and turn it on as the source server. Boot into OFW, the other XO-1s you want to reflash, and tell them to receive a new image. I think there was a key shortcut of some kind that told a machine to receive. The server XO would continue to send packets until all other machines had received enough packets to make up a complete disk image. If I remember correctly, they used it to reflash 3000 machines in the field that I heard about. There may have been more elsewhere or since.

Damn Cool Algorithms: Fountain Codes

Related Stories