Computers can mimic nature and outperform themselves
Indranil Gupta
Nature has evolved over millions of years, and its creatures have found very efficient ways to thrive. Digital computers, on the other hand, are dependent on us humans, and they have "evolved" only over the last sixty years or so. Computer scientists like Professor Indranil Gupta are looking at borrowing ideas and principles that govern natural phenomena and applying them to computer systems. Most computer systems are distributed, meaning they have multiple nodes. The Web, the Internet, peer-to-peer networks, and databases are all examples of distributed systems. So are colonies of bees and ants, flocks of birds, and herds of sheep. Gupta is extracting the behavior of animals and designing nature-based distributed systems that are effective in solving interesting problems. These problems range from designing secure file systems to fast grid computation and managing large-scale clusters of PCs.
Gupta designs distributed systems in a very systematic way,
first by making mathematical models of natural systems using
differential equations. From those, he can develop a set of
techniques that take the mathematical models as input to design a
distributed system. It turns out that when these differential
equations are inserted into the distributed system design, the
result is the same as what happens in nature. What has surprised
and delighted Gupta is that these design methodologies are
well-suited for solving some interesting problems in distributed
systems, and that some of his nature-based systems outperform
current computer science systems that have been
hand-designed.
Honey Sort
Honeybees are the source for Gupta's novel sorting method based on bee behavior that works well for grid computing. Gupta has leveraged the bee's ability to interact with its environment and with other bees as well as its ability to make good decisions that ensure the life of the colony. Bees do not randomly flit about from flower to flower looking for nectar. Instead, they rely on each other to point out good nectar sources. When an individual bee finds a good source, he will perform a little dance (flying around in a figure-eight, for example), whose orientation lets other bees know the direction of the source. The better the source, the more excited the bee is, which he shows by dancing for a longer time. He might do five figure-eights for a ho-hum flower and ten for a really good one. Other bees are more likely to spot the bee doing the ten figure-eights simply because the duration of the dance is longer. These other bees will statistically decide to go to the really good nectar source until it is exhausted.
Now extend this setup to a distributed computer system. Instead of bees, we have PCs, and the nectar sources are represented by different programs that the PCs can run on the dataset given to them. For instance, to sort a large database, one nectar source (program) may be Quicksort. Another may be Insertionsort. Programs are ho-hum or good depending on how fast they perform. Without the honeybee mechanism, the PCs have no way of knowing which of the nectar source (program) is fastest for a given dataset. However, suppose the PCs talk to each other like the bees do with their dancing? Just as the honeybees quickly converge to the better nectar source, the PCs will decide amongst themselves which program is the faster one.
This honeybee mechanism, called HoneySort, has been
implemented by one of Gupta's former students Yookyung Jo and has
been deployed in the Computer Science Instructional Laboratories
and in experiments. Most surprisingly, experiments reveal that
HoneySort is faster than the traditional parallelized versions of
both Quicksort and Insertionsort, both of which are traditional
programs and are already considered among the fastest existing
sorting programs. "So, computers can mimic nature and outperform
themselves!" exclaimed Gupta.
MON: Management Overlay Networks
MON, or Management Overlay Networks, is a project Gupta is
working on with Professor Klara Nahrstedt. The main idea behind
MON is to manage clusters of servers, such that when an application
is run on the cluster, the user will be guaranteed a certain level
of service. To implement this, one of the ideas is to borrow the
phenomenon of epidemics from nature. We all know how information
spreads in among humans: rumors spread in society, and diseases
spread in populations. These spreading processes happen quickly,
comprehensively, and automatically. The MON project harnesses this
powerful mechanism for useful purposes. A company might run a
server farm with a couple hundred machines that host thirty to
forty websites. Alternately, a global-scale cluster such as
PlanetLab may be running distributed applications like DNS. In
such a large cluster of PCs, a user or administrator may want a
guarantee that thirty machines in this cluster will always be
running a particular program. When a link goes down or a bug
arises, you want the system to manage itself, and what needs to be
done is specified upfront by the user. MON fills in "how" these
user-defined management actions are implemented. MON can also be
used for reconfiguration on failures and to query your distributed
system. You may want to ask it: "How many of my original thirty
nodes are up right now?" If one is down, do you want it to do
anything about it? If five are down, do you want to create another
five? These are the kind of management decisions the cluster will
make automatically according to your specifications. When you query
such a system, the questions and the answers are spread and
collected using epidemics. If you ask the MON system a question,
it will get you the answer, even if several nodes have failed or
several links have collapsed. It gets around these failures by
using the epidemic mechanism.
Folklore
There are several methods for content distribution on the
Web, both of which borrow terms from viruses-the kind that make us
ill. MON uses the epidemic method, also known as the Gossip
Protocol. With epidemic content distribution, information spreads
from one machine to another. Everyone gets it, and that's it.
Another method is endemic, which behaves like influenza, in which
you contract the disease, recover, and then become receptive to
infection again. In this case, only a small fraction has the
disease at a time, but it's very difficult to get rid of. The
protocol is a distributed design system or algorithm. Now, replace
each person with a PC, and each virus (epidemic or endemic) with a
file. When a file is inserted into the system, it cannot be
eliminated because it is constantly moving around. One of Gupta's
PhD students, Ramses Morales, has written a distributed file system
called Folklore, which improves upon the endemic protocol to create
a distributed backup storage scheme. "Here we are using techniques
that virus writers use but for good purposes," said Gupta.
Overhaul
Gupta's project Overhaul fights flash crowds at websites. Flash crowds, also known as the "slash-dot effect," are cyber versions of crowds that suddenly flock together to, say, a celebrity sighting or car wreck-if there are too many people, you can't see a thing. The term flash crowd is from the 1971 novella by the same name by Larry Niven in which a whole bunch of people wanted to teleport to the same place at the same time. In the case of an overcrowded website, the result is denial of service. Flash crowds at Victoria Secret's first multicast and at CNN's website on 9/11 overwhelmed content provider's Web servers and essentially shut the sites down. Overhaul, written by Gupta's graduate studnets Jay Patel and Charles Yang, solves the flash crowd problem by masking the servers predicted to fail and by using client replication. When the detector running at the server detects a flash crowd coming, it goes into flash crowd mode. In this mode, links among clients are maintained and the server decides which client can fetch the data. Then the other clients fetch the data from the lucky client that got through. If that client is overwhelmed, another can still access the server. Overhaul works because it uses the "wisdom of the crowds" - clients help each other fetch content at times when the server is stressed.
"Research on these nature-inspired designs for distributed
computer systems is a good mix of theory and experimental, rather
than merely simulated, results. That's what I like most about this
research. In most research projects, you design a system and hack
it up. It works, you go away, and no one really learns anything
from it. But things we have learned with these nature-inspired
projects will still be around even after the project is over," said
Gupta.
Written by Judy Tolliver,
February 17, 2006
--
Last Modified August 07 2006 08:59:20.
