Find John Fast!!

The popular paradigm of the computer is a web client, and large chunks of the software development effort is connected to web development. But Tracey and I are still trapped with the notion of the computer as a problem solver, not as part of the solution but as a solver. We use the computer to solve hard problems and we currently are trying to solve unsolvable problems.

In both cases we are struggling with Level 1 parallelism (see Figure 1). We are pursing a suspicious possibly spurious connection between problem complexity, search, and Level 1 massive parallelism.

In Level 1 parallelism, we are concerned with the inherent complexity of the problem, not necessarily the complexity of some algorithm used to solve the problem (see Figure 1). This can be a tricky distinction. Through either poor choice or poor programming I could come up with an overly complex algorithm for a simple problem. For example, I could come up with a search strategy that took exponential time to search a list that is in alphabetical order. It is well known that there are solutions to the problem of searching a ordered list that require far less work than any exponential search strategy. Binary search is a case in point. Even a brute force from start to end of the list search only requires that we look at each item in the list once. So in Level 1 parallelism our focus is not on the complexity of some algorithm we might choose to solve the problem, but on the complexity of the problem itself.

For example, our problem is to obtain tomorrow's winning lottery number from John Smith who is currently on Main Street somewhere in the United States. The winning lottery number happens to be the same as a telephone number + a three-digit office extension on one of the business cards that he has in his possession. Unfortunately, John doesn't know that he has the winning lottery number. Of course many of the issues in this problem are obvious. Where in the U.S is John? Which city? Further, which Main Street in that city? East Main? West Main, etc.?

Not only do we have to find the city and the correct Main Street, we also have to find which John Smith. Perhaps there is more than one John Smith currently standing on some Main Street in the U.S. After we have tracked down John Smith, we've got to see what business cards he has in his possession and which ones have phone numbers with 3 digit extensions. And then if there is time to buy lottery tickets before tomorrow's drawing!

There are lots of strategies that we could use in trying to accomplish our goal. Each of those strategies have their own complexities. But we are more concerned with the inherent complexity of the problem itself. Although this problem suggest extremely obvious applications of parallelism (embarrassingly parallel in this case). Is massive parallelism sufficient? What if there are tens of thousands of John Smith's currently on Main Street somewhere in America? What if most of those John Smiths are salesman and have thousands of applicable business cards in their possession? How do we distinguish our John Smith that's currently on Main Street somewhere in America from all of the other people who are currently on Main Street somewhere in America? Can we obtain the winning lottery number from John Smith before tomorrow's lottery drawing? What level of parallelism would make that possible? How would that parallelism be structured or organized? How would the parallelism be managed?

Keep in mind that we've made no mention of computers. Level 1 analysis and decomposition happens before computer solutions are modeled. The paradigm shift requires not only rethinking parallel approaches but also rethinking our approaches to problem and solution modeling. But yet there is hope from the ghosts of ICOT and the Fifth Generation project. Stay tuned.