Simply put emergence is the creation of complex structures through simple interactions. In a strict definition, in order for a process to be considered emergent, it must be difficult or even impossible to predict the highest level of a system given its low level processes. Nature provides many interesting and powerful examples of emergence.
The quintessential example of emergence stems from the interactions of ants in a colony. Have you ever wondered why there was a thick line of ants running through your kitchen? This line is a direct result of emergence. To find the shortest path to a food source ants rely on the power of emergence. Through the simple interactions of randomly scouring for food, and then through the laying of pheromone trails, ants are able to create an emergent system to find the optimal path to a food source.
Ants find an optimal path by laying a pheromone trail, a chemical message, from a food source to the colonies nest. Obviously, the shorter the path to the food source, the more ants that can cross the path in question in a certain amount of time. The previous sentence describes the entire algorithm that ants use to find a shortest path. Something that takes complex math for humans to do, can be accomplished by ants through simple interactions. Since more ants can cross a shorter path in a given amount of time, the pheromone levels of that path become stronger, due to the sheer number of ants laying down a trail. Ants leaving the nest will pick the path with the highest pheromone level, there by picking the shortest path to the food source.
So you may be thinking, well it is great that ants can do this, but does emergence have any value to computer science. The answer is a resounding yes. It is interesting to note that the above example, of how ants find the shortest path to a food source, is being used to implement faster and more reliable data communications routing systems. In these systems, virtual ants move from router to router on a network and leave electronic pheromone trails that keep track of the shortest path and that control the level of congestion. When data packets are routed, they will follow the network link with the highest electronic pheromone value, thus taking the shortest path. Congestion can also be controlled by using the above ant example and applying it to communications routing. When a link gets too high of a pheromone level, meaning the link is becoming congested, the link with the next highest pheromone level can then be used.
In most computer programs that attempt to use emergence to solve optimization problems, such as communication routing, randomness plays an important role. Randomness provides the engine that drives emergence. However, as can be seen by comparing the various versions of the four color graph problem, too much emergence can be just as bad as not enough. Well randomness provides the driving force behind emergence, too much can cause the system in question to enter a useless chaotic state where the system goes out of control.