Swarm Intelligence

In a previous post on the Honey-bee algorithm for allocating servers, which I found quite fascinating, I had pointed out I had referred to a paper on Swarm Intelligence by Eric Bonabeau and Christopher Meyer published by Harvard Business Review, and finally I got time to go back and read it and I found it quite fascinating! The paper describes case studies where people have used algorithms inspired by nature (ants, bees) which use a decentralized model of computation and optimization.

The paper points out that the main advantages of using algorithms like these are flexibility, robustness and self-organization. The algorithms work in a completely decentralized manner, and work on the principle that the wisdom of all the ants (or the small agents) can be harnessed in such a manner that the whole is far greater than the sum of its parts. Also, the algorithms are invariably robust to failure and adaptive since they don’t make use of a central decision making bodies and there is a lot of experimentation with new sources of food (or results in the case of algorithms).

The paper also points out that there are several cases where these concepts have been used successfully (both in business and academia):

  • Optimally routing telephones calls and Internet data packets seems to be a tough problem because if we use a centralized algorithm, it will neither be robust nor adaptive. Algorithms based on swarm intelligence come to the rescue since they are not based on a central decision making body, but rather work on the principle that the scouts recruit other agents to follow new promising paths.
  • Fleet management and cargo management also suffer from similar problems. The paper points out that Southwest Airlines found out that in some cases, letting cargo go to wrong destinations and recovering is faster and more robust than always making sure that all cargo is handled correctly.
  • Small simple rules that lets people take decisions for themselves usually works best. This has since been shown to work very well for companies such as Google as well.

There are more case studies in the paper, but what’s fascinating is that these techniques become even more popular now-a-days because companies have realized that it is easier to tolerate failure than to eradicate it — more so in the context of the Internet where there is a race to build systems that are self-correcting (such as Map-Reduce, Hadoop and Dryad). Also the new realities of the emerging architectures (multi-core, highly parallel, massive clusters grids) is going to mean that we have more parallel horsepower to run our applications and such self-organizing algorithms are going to become even more popular in the computing community.

However, one concern would be programming models for such computing bedrocks. We still don’t understand how to manage parallel computation very well to ensure that interpreting such algorithms in code is going to remain difficult for the average programmer for quite sometime.

Honey Bee Algorithm for Allocating Servers

I came across an interesting article in The Hindu (see the story from GaTech news; I couldn’t find the link on The Hindu website) today which described work done by Sunil Nakrani and Craig Tovey, researchers in GaTech, on using a decentralized profit-aware load balancing algorithm for allocating servers for serving HTTP requests for multiple hosted services on the Web. The interesting, thing is that the algorithm is based on how Honey Bees in a bee-hive decide where to collect nectar from. I decided to take a look at the paper.

Essentially, the forager bees collect information about how profitable a particular nectar source and how much is the cost involved in collecting from that source (round trip time). Based on a composite score, they perform a waggle-dance which essentially indicates what is the value of performing foraging where they have been. The inactive foragers can thereafter figure out where to go look for nectar.

The researchers modeled it in the server space by having an advert-board, where servers post profits from serving a request and the time required to serve it. Thereafter, the other servers can choose which colony (or service) they wish to be a part of. Existing servers can also move to another colony based on a probability determined from a look-up table indexed by the ratio of their profits by the profits of their colony.

Their results indicate that they do quite well compared to optimal-omniscient strategy (which knows the pattern of all future web requests) and better than existing greedy and static assignment strategy. Shows that we still have a lot to learn from nature!

One thing that flummoxed me though was that the original paper seems to have been published way back in 2003 (see Tovey’s publication page). I wonder why it got press publicity only now.

[The paper also cites a Harvard Business Review paper titled Swarm Intelligence: A whole New Way to Think About Business]

Follow

Get every new post delivered to your Inbox.

Join 1,843 other followers

%d bloggers like this: