Emergence

Suppose, you are going to develop a traffic control system for a rather large city. The goal is to optimize traffic throughput which could be measured by average miles of each cyclist and motorist. In a first approach, you may suggest to use a purely centralized control subsystem.

There are various problems with this task:

• In a rather large traffic infrastructure, traffic can never be controlled from a centralized component. First of all, this component would represent a single point of failure. Secondly, it would not scale or perform at all due to the sheer amount of traffic signals involved.
• The requirement of traffic optimization reveals a significant problem. Assume, that there is a main road through the city. The best way to achieve the goal could be to just set all traffic lights on the main road to green. Participants driving on side streets would then need to wait forever. That's what is called starvation in multithreading.

How could we solve those problems?

• Instead of using a centralized approach, we could rely on a completely decentralized approach. For example, each street crossing could permanently measure the traffic and adapt its traffic lights automatically to the current situation. If all street crossing act independently, local tactics might dominate global strategy. Obviously, this is not what we want. Strategy should always dominate tactics. Hence, let local decisions of street crossings depend on "neighboring" street crossings. If appropriate, we could also mix centralized control with decentralized autonomous adaptations. That basically means, that we control the overall strategy, but allow the system to automatically and locally adapt its tactics. Is it always useful to apply decentralized approaches? No. Here is a real life experiment: Take a number of people in a row each of them stretching one of their fingers. Put a large stick on their fingers. And then tell the group to systematically and gently put down the stick to the ground. They won't succeed until finally one person will become the leader and coordinate the whole action.
• We also learn from the example that we need really to address requirements with much more care, especially in systems with complex interactions. In the example above the target function should not only consider average flow but also take possible starvation into account. By the way, the traffic example could also be replaced by a Web shop and Web traffic.  In this example, starvation would imply that some shoppers would have a fantastic experience while others could not receive any Web page in an appropriate response time. Guess, how often the latter ones would re-visit the shop. Wrong understanding of requirements can seriously endanger your whole business goals. 

The question is how to design such decentralized systems. There are lots of options:

• Infrastructure: P2P networks are one way to organize resources so that they can be located and used in a decentralized way. Cloud Computing formerly known as Grid Computing is another cool example.
• Algorithms: Genetic algorithms help systems to automatically adapt themselves to their context.
• Cooperation models: Swarm Intelligence such as ants also illustrates how emergent behavior can substitute centralized control.
• Architecture: Patterns such as Leaders/Followers or Blackboard help introduce decentralized approaches.
• Technologies: Rules engines and declarative languages such as Prolog are useful for providing decentralized computing.

The problem with decentralized versus centralized systems is often when to use what. And in addition, to decide how much decentralized the system should be. This is not always obvious. Let me give you some examples instead:

• In a sensor network you might place many small robots to a specific area in order to monitor environmental data. These robots would be completely autonomous. Even if some of them fail, the overall system goal can be achieved.
• In a Web Crawler several threads could search for URLs in parallel, but they would need to synchronize themselves (e.g., using a tuple space) in order to prevent endless loops. This resembles ant populations.
• In a car or plane you need central control, but some parts can also operate and adapt  independently such as Airbags or ESP. This is more a hybrid approach with the global strategy implemented by a centralized approach.
• In embedded (real-time) controllers (such as your mobile phone) everything typically is centralized  because behavior must be statically predicted and configured.

The more co-operation your components require and/or the more determinism you need, the less a decentralized approach seems appropriate, and vice versa. 

The best way to design such decentralized systems is to introduce the concept of emergent behavior. For example, define a set of simple local rules to which the system parts must abide. And then let the parts take control.  By the way, this is exactly how the Internet works. But in the Internet, you will also find a hybrid approach combining centralized backbones with decentralized nodes.