Unite and Prosper algorithms

When we study algorithms we study a paradigm of problem-solving called "divide and conquer". This approach to problem-solving involves breaking down a complex problem into simpler components and solving each of them separately, and then combining the solutions. Divide and conquer as an algorithmic technique is widely popular, and is easily amenable to parallelisation. 

Deeply rooted in Indian history however, I have a mental block-- some kind of a cultural aversion-- against the concept of divide and conquer, because of what this strategy has done to us when we were at the receiving end. Whenever anyone extolls the joy of divide and conquer-- even in a purely algorithmic context-- I find myself cringing uncomfortably. 

But regardless of my personal views about this paradigm, divide and conquer as a strategy is also based on a simplifying assumption that the combining of individual solutions to get the overall solution is a trivial problem. This need not always be the case. In fact, combining individual solutions to form the global response may sometimes make the global problem worse. 

The class of "sustainability" problems are good examples of such a dilemma. Consider a population of car owners who use fossil-fuel cars to commute daily. Due to some global crisis, fossil fuel becomes costlier, and the government wishes to reduce fuel usage. It then adopts a divide and conquer strategy, where in order to improve reduce overall fuel usage, it mandates that all individual cars need to become fuel efficient and use less fuel for the same tasks. Let us say it succeeds in this endeavour and individual cars improve their mileage. A car that used to once give 10 kms to a litre of petrol would now give, say 30 kms to a litre. So, does this mean that the government has succeeded in reducing its reliance on fossil fuel? No! Since mileage of individual cars have increased, individual car owners would now be more likely, rather than less, to use their cars even in cases where they preferred not to use them before. Increased usage of cars increases demand for more cars, and eventually, fuel usage goes up, rather than down! 

In most cases, what works for the individual cannot be directly scaled to the collective as a solution. The problem of scaling from the individual to the collective, is not at all trivial, and requires new paradigms of problem-solving. I'm generally calling this as the "unite and prosper" paradigm of problem-solving. 

A number of distributed algorithms fall in this category. Algorithms that explain the spontaneous emergence of synchrony in coupled oscillators are an example of the "unite and prosper" paradigm. Similarly, distributed constraint optimisation, global snapshot computation, resilient distributed consensus, etc. all address problems of combining fragmented knowledge to find a global solution, and can be thought of as examples of the "unite and prosper" paradigm. Unite and prosper, looks for solutions where both individuals and the collective, have solved the problem sufficiently well. 

I am of the strong opinion that we need to study this paradigm of problem-solving as a separate topic of study in its own, which may reveal a number of deep insights into complex network interactions. 

Let me end this post, with a "unite and prosper" puzzle for the reader: 

There are n people in a group, each having a piece of knowledge. Whenever two persons interact, they share everything that they know with the other. Given this, answer the following: (a). What is the minimum number of interactions for everyone to know everything? and (b). What is the minimum number of interactions for everyone to know that everyone knows everything?