I think I first saw this hack in an obfuscated programming contests where in it was used to implement the tape of a Turing machine. A Turing machine runs it’s tape both forward and backward. If you simulating that one obvious possiblity is a doublely linked list where each node holds a pointer to both the next node and the previous node.

So in node B you store a pointer to A and C. The hack saves memory by xoring A and C together and storing that. This works because as you travel foward along the tape and you arive at node B you will have just left node A so you can xor the stored A+C with A and out pops C. And you can do the same thing going in the other direction. Of course if you arived at node B via any other route the the A+C value is useless. For example you lose the ablity to delete B from the tape given a random pointer to it. I’ve never found a practical application of this hack other than saving space and obfuscating code. I’ve never ran into an application other than a Turing machine where I wanted messages that could be read forward and backward; though now that I’m thinking about it there might be some cases involving undo/redo.

In anycase I was reminded of this by looking at some of the schemes used in peer to peer distribution systems. In some of those systems the message is fragmented by the publisher and scattered across the the swarm of clients. They then collaborate to reassemble the message. It’s better if you can arrange things so that the lose of a few fragments doesn’t make it impossible to reassemble the message. A scarce fragment, like a patent on a key element of a standard, can frustrate the entire swarm. This makes the system brittle and raises the stakes for getting the coordination right.

The publisher can solve that. He can pump up is output and provide some redundent info. That removes the scarcity, relaxes the need for perfect coordination. Brittle no more. The easy idea is he just distributes multiple copies of the content; but consider this trick. Just as a very primitive example. The publisher breaks the content into two fragements A and B. He then ships three packets: A, B, and A xor B. Consumers can then reassemble the content given any two of the three packets.

Here some links: used in streaming, used in file transfer, pretty picture the example above.

Getting the publisher’s content moved thru the swarm is the same problem as getting a message passed thru a lossy channel. That problem that’s gotten a lot of attention for the last 50+ years. The world is full of lossy channels so if you go look at any heavy used lossy channel you’ll find tricks of the trade for solving this problem. Netnews for example. When clueful people (and pornographers of course) distribute large files thru netnews they use special archive formats that include a set of PAR or Parity Sets that provide redudency for to enable the consumer to reconstitute the archive given only a subset of the messages that dispatched it.