OpenP2P.com    
 Published on OpenP2P.com (http://www.openp2p.com/)
 See this if you're having trouble printing code examples


Swarms and Mobs at This Year's ETech

by Daniel H. Steinberg
04/25/2003

Timing is everything. Hundreds of great ideas flit through your consciousness every day. What makes one stick out? Often it's a convergence of ideas. A particular idea stands out because another provides a new context for it. That's the real power of a gathering such as this year's O'Reilly Emerging Technology Conference.

Individually, Eric Bonabeau's keynote on Biological Computing and Howard Rheingold's address on Smart Mobs would have been interesting. Taken together you can see the application of emergent behavior described by Bonabeau to the technological challenges issued by Rheingold.

Bonabeau begins his keynote by considering Kevin Kelly's statement that "Dumb parts, properly connected into a swarm, yield smart results." Bonabeau explores bottom up design where the component parts are programmed with simple behaviors that result in complex aggregate behavior. Rheingold points out the power of self-organizing networks and provides examples of projects that were accomplished with distributed, decentralized, collective action instead of in a top down controlled manner. Bonabeau presents case studies of difficult problems for which swarm algorithms provided robust solutions.

Bio-Inspired Computing

Eric Bonabeau's follows the Kelly quote by asking how we might properly connect dumb parts properly into a swarm. He suggests that the inspiration might be found in nature. The immune system, bacteria, and the brain are examples from nature of a collection of relatively simple constituent parts that collectively demonstrate sophisticated behavior. The idea of bio inspired computing is to look at and emulate examples from nature.

Social insects provide much of the inspiration for swarm computing. Groups of social insects are able to accomplish tasks that no single insect is able to. Because social insect behavior has been shaped by millions of years of evolution, it is a rich resource for computer scientists looking to define swarm algorithms. Bonabeau notes that successful and resilient solutions are flexible, robust, decentralized, and self-organized.

Eric Bonabeau.
Eric Bonabeau explores bottom up design where the component parts are programmed with simple behaviors that result in complex aggregate behavior. Photos by Derrick Story.

Bonabeau stresses that "what is really important in this field is the decentralized/bottom-up mindset. The main message is that the small intelligence movement is all about looking at the world from the bottom up. You have to look from the point of view of the constituent systems."

Rheingold Urges Technological Activism

"Our ability, our freedom, to innovate," begins Howard Rheingold in his keynote address, "is not necessarily going to be as unbridled in the future as it was in the personal computer and internet era." Rheingold, author of Smart Mobs: The Next Social Revolution, acknowledges that there is a place for political awareness and activism. "But," he says to the Wednesday morning audience, "there are people in this room who can innovate our way out of or around the technical and political regulatory enclosures that are being put into place around innovation.

Rheingold cites the RIAA, the MPAA, and Internet radio as instances of incumbents using their political and economic clout to block or thwart newcomers. He says that "we need to fight for a preserve in which there will be a rich network of devices, media, and electromagnetic spectrum available for experimentation." He says that with Napster seventy million people voted with their modems that was how they wanted music. This was an example of a business model of incumbents threatened by a disruptive technology. The problem with Napster, Rheingold explains, is that there was no model for fairly compensating artists. He argues that we should invent a way to compensate artists and innovate our way out of this political suppression of innovation.

Cory Doctorow.
Cory Doctorow points out that distributed "ownership" models have changed the world.

Cory Doctorow follows on this theme in the morning panel discussion of DRM in Practice: RIghts, Restrictions, and Reality. Cory also acknowledges the need for compensating artists for their work. But, he points out, when Napster was shut down, distributable computing sites popped up elsewhere. He points out that this distributed "ownership" model changes the world. He challenges the audience to imagine that within days of the library at Alexandria burning, other libraries began sprouting up using the technology of the day to replicate the content that would have been otherwise lost in the fire.

Lessons from Bio-Inspired Computing

Bonabeau presents lessons and examples from nature that are important in swarm computing. The first lesson is Emergence: The whole can be more than the sum of its parts. He is careful to note that the sum need not always be more than the sum of its parts, just that if you design carefully this can be true. His examples include ant colonies looking for food when more than one path is available. Ants leave pheromone trails and so the quickest ants to return with food are laying down and reinforcing trails that subsequent ants will tend to follow. Unfortunately, this simple algorithm isn't robust. If a shorter path is introduced after there has been significant ant traffic using a longer path then the well traveled path will contain a high enough concentration of pheromones that it is unlikely the ants will discover the shorter path. A simple addition to this model is evaporation. If the pheromones evaporate then it becomes more likely that newly introduced optimal routes can be discovered and reinforced.

Bonabeau warns that "there are three things you don't do in public, and one of them is mathematics." He then presents an application of this ant pheromone/evaporation algorithm to use traveling sales ants to solve the traveling salesman problem. Not only does the algorithm work, but it compares well to other optimizations and heuristics. The real power of the ant algorithm is that you end up with more than just one solution and that if some of the cities and paths disappear and the problem needs to be configured, you can find a solution to a new solution quickly. Unilever has used this type of algorithm to schedule production scheduling. MCI and other companies have used these algorithms for routing communications networks.

The second rule is Simple rules rule. As an example, Bonabeau presents a bucket brigade model for harvester ants. The first and smallest ant carries a seed from the source toward the nest until it meets a larger worker. The larger worker takes the seed and starts back to the nest while the smaller ant heads back to the seed source for another. The larger ant continues until it finds an even larger ant and so on. At Georgia Tech, industrial engineers showed that this is a good way to organize labor. Taco Bell has adopted their research. Imagine workers all begin filling their respective orders. The fastest worker finishes first. The algorithm is for that worker to take over the work from the next fastest worker who takes over the work from the next to next fastest worker and so on. This algorithm was also implemented at Revco Drugstores (now part of CVS) resulting in a 34% increase in efficiency.

The third rule is No one needs to be in control. Bonabeau was able to model the building of wasps nests. The idea is that no wasp knows how to build a nest and yet collectively they build fairly complex structures. He modeled virtual agents and bricks that resulted in complex and interesting virtual 3D nests. There is a problem with blindly following simple rules. Sometimes you can end up in a pathological situation. One example are ants that have managed to form a loop around a tree. They are laying down pheromones and reinforcing a non-productive path and the collection ends up dying of exhaustion.

A fourth rule is Size matters. Small colonies of social insects tend to be polyvalent. All tasks are performed by everyone. As the swarm size grows you will see specialization and the swarm gets more efficient. There is an inflexion point at which the marginal increases to efficiency begin to decrease. At some point after that there is a point at which bees, for example, will de-merge and return to the stage at which growth is beneficial.

Collective action

Rheingold encourages developers to think ahead to a world where people carry computers that are all wirelessly connected and always on served up by plenty of bandwidth. Peer to peer is not just about file sharing. You can also share computing power and information like the SETI@home and folding@home projects. SETI has between thirty and forty teraflops of computing power. Think of applying the swarm algorithms from Bonabeau's talk to these swarms of machines.

Howard Rheingold.
Howard Rheingold points out the power of self-organizing networks and provides examples of projects that were accomplished with distributed, decentralized, collective action instead of in a top down controlled manner.

Rheingold recommends designing technologies for this world of billions of people carrying devices with them that are networked and pervasive. Already, more people today carry internet terminals with them than use the internet from the desktop. As an example, fishermen off the coast of India get messages telling them which port has fish in it today. The challenge is to design the systems so that they are open and enable self-organized groups that create things we don't know about yet.

In order for people to band together, you need to have trust mechanisms. Imagine you are at the airport and could find people who could either offer a ride to where you needed to go or needed a ride to someplace you are going. If you could somehow have confidence that you can trust the other person you might be happy to offer or accept a ride. A reliable reputation mechanism might be the programming key that allows emergent social applications. The more richly linked the system is, the more options there are. Like Bonabeau's swarms, Rheingold recommends eschewing centralized control and allowing and encouraging people to hack what you build.

Daniel H. Steinberg is the editor for the new series of Mac Developer titles for the Pragmatic Programmers. He writes feature articles for Apple's ADC web site and is a regular contributor to Mac Devcenter. He has presented at Apple's Worldwide Developer Conference, MacWorld, MacHack and other Mac developer conferences.


Return to the OpenP2P.com.

Copyright © 2009 O'Reilly Media, Inc.