View source for Self-assembly for discreet, fault-tolerant and scalable computation on internet-sized distributed networks

{{ThesisTemplate
|title=Editing Self-assembly for discreet, fault-tolerant and scalable computation on internet-sized distributed networks
|abstract=When engineers compare biological and software systems, the former come out ahead in the majority
of dimensions. For example, the human body is far more complex, better suited to deal with faulty
components, more resistant to malicious agents such as viruses, and more adaptive to environmental
changes than your favorite operating system. Thus it follows that we, the engineers, may be able to
build better software systems than the ones we build today by borrowing technologies from nature
and injecting them into our system design process.
In this dissertation, I present an architectural style and accompanying implementation support
for building distributed software systems that allow large networks, such as the Internet, to solve
computationally intensive problems. This architectural style, the tile style, is based on a nature's
system of crystal growth, and thus inherits some of nature's dependability, fault and adversary
tolerance, scalability, and security. The tile style allows one to distribute computation onto a large
network in a way that guarantees that unless someone controls a large fraction of the network,
they cannot learn the private data within the computation or force the computation to fail. These
systems are highly scalable, capable of dealing with faulty and malicious nodes, and are discreet
since every su�ciently small group of nodes knows neither the problem nor the data.
The tile style is based on a formal mathematical model of self-assembly. In order to leverage this
model to build software, I de�ne the notion of self-assembling computation and develop systems
that compute functions such as adding, multiplying, factoring, and solving NP-complete problems
SubsetSum and SAT. For each system, I prove its correctness, compute its probability of successful
computation, and show that its running time and tileset size are asymptotically optimal.
I use the mathematical nature of the tile assembly model to present a formal mathematical
analysis of the tile style, proving that software systems built using this style are discreet, fault- and
adversary-tolerant, and scalable. I further implement a tile-style system and use it to distribute
computation to empirically evaluate the tile style's utility.
|authors=Yuriy Brun
|date=2008/05/01
|file=[http://www.cs.washington.edu/homes/brun/pubs/pubs/Brun08PhD.pdf PDF]
}}