01.28.07
Avoiding the n-squared catastrophe
The n-squared catastrophe (Metcalfe’s Law) occurs while messaging many other nodes in a cluster. I knew this math since 5th grade at West Elementary.
1 0
2 1
3 3
4 6
50 1225
This is also a game of connect the dots. How many lines are required to connect all dots to all others? n*(n-1)/2.
If there are 4 students in a class they need to pass 6 pairs of notes to each other to communicate. With 50 students, 1225 pairs of notes must trade hands. This is getting out of hand. Soon, instead of performing important tasks, the entire school day is taken up by note-passing. Surely there is a better way.
Computer programmers are slow to learn this lesson. This is mainly a lesson of a multi-node setup. Most coders like to think of complex problems in terms of a single application. A multi-node setup is never like a single application due to the above scaling law. Consider the code.
int count = 0; // a global
That’s all. It’s a global. In a single application, you would not dream of attempting to sync multiple variables, count1, count2, etc. Why would you do this with multiple nodes? The obvious choice in an application is to create a global or static variable. The obvious choice in a multi-node setup is to use a single centralized database. The n-squared catastrophe will kill you otherwise.
Dave