Thanks for the memory

tauringhuang.

Sep 10th 2008
From Economist.com

A mathematical trick may allow people to scatter their computer files across the world's hard disks

Wuala

Scatter brainsIF YOU have lots of unused storage space on your hard disk, then why not share it with others on the internet? The benefit could be distributed storage for your own files, making them available any time via the web, even if you are nowhere near your computer—indeed, even if your computer is switched off. That desideratum is what a Zurich-based firm called Caleido is aiming to provide, with a free online storage service known as Wuala that was recently introduced to the public.

Though the idea underlying it is simple, Wuala requires some nifty technology to make its distributed system work reliably. In particular, its developers, Dominik Grolimund and Luzius Meisser, have used a clever mathematical trick to compensate for the fact that the participating computers will come and go from the internet in an unpredictable way.

The challenge is how to minimise the number of copies of the same file that have to be distributed. Copying costs participants both storage space and bandwidth. Yet there have to be enough copies to ensure that there is at least one available most of the time. If, for example, each computer is online 25% of the time, then a quick calculation shows that you would have to copy each file to 100 different computers to ensure that 999,999 times out of a million there is at least one copy available when a user looks.

But copying every file a hundred times is hugely inefficient. Instead, Mr Grolimund and Mr Meisser plan to break each file into chunks, which can be scattered liberally around the hard disks of participating computers, and then to use a mathematical trick to reconstruct the original file from those chunks.

tauringhuang.

This trick, known as Reed-Solomon error correction, is employed routinely to interpret the data on DVDs, but it has not been used before in the volatile world of private computers on the internet. The first step is to convert the file (which is, regardless of what it represents, simply a long string of ones and zeros) into a mathematical function called a polynomial. This is done by splitting it into 100 fragments, which are smaller binary numbers. It is these numbers that are used to define the polynomial.

One of the characteristics of a polynomial is that a few numbers can nail it down precisely. If a simple polynomial is plotted out on a graph it forms a line. A straight line (the simplest type of polynomial) is defined by any two points on its length. A parabola can be defined by three points. The polynomials that Wuala generates can be defined by 100 points—though, because the polynomials used are not simple ones, these points are complex mathematical constructs, rather than straightforward numbers.

All you have to do now, therefore, is select a suitable number of points from along the polynomial (these need not be the original ones) and convert their values into the appropriate mathematical constructs. Scatter these around the host computers and, when someone wants to look at the file, he need recover only 100 of them to have enough data to reconstruct the file from scratch. To have 100 points available 999,999 times out of a million it turns out that you need to scatter a total of 600 of them around. That is an amount of data equivalent to six versions of the original file, rather than the 100 that would be needed to achieve the same level of reliability if whole files were being stored. Moreover, the system needs the computers linked to it to be available for only 17% of the time, rather than 25%, for this to apply.

Online storage is a growing market, especially for backing up data, where reliability is a big concern. Most commercial online-storage services use centralised servers. Although these are generally reliable, they do sometimes fail. And when they do, the results are embarrassing—as Amazon, an online shopping company, learnt on two occasions this year when the servers for its commercial data-storage system went down for several hours at a time.

tauringhuang.

Though some people may feel squeamish about scattering their data over hundreds of other computers (even though it will be encrypted), or storing unknown file fragments on their own, Mr Grolimund is adamant that Caleido has learnt from other “peer-to-peer” file-sharing systems, and that Wuala is built to handle concerns about the illegal distribution of copyrighted or “inappropriate” content. If he is right, Wuala may prove that, for online data storage, it is as good to give as it is to receive.