Partitioned Complexity

Roger Sessions has some good material I wanted to take a moment to highlight.  This is part of his work around  a new Enterprise Architecture framework, Simple Iterative Partitions (SIP).

Correlating Complexity to State

First, let’s look at how complexity grows based on the number of significant states in a given program.  I’m not a math geek, so we are going to go with an oversimplified example.  If you are a math geek, feel free drop a note in the comments for whatever reason.

In his example, we first look at a coin-tossing application.  In short, the requirements state that the program should detect a coin-toss and inform the user if the coin landed heads or tails up.  The user will be dropping their penny into a specially designed sensor which our program will read data from.

Here’s our pseudo code:

PennyState state = sensor.GetState();

if (state == PennyState.HeadsUp)
{
   MessageBox.Show(“Heads Up”);
}
else if (state == PennyState.TailsUp)
{
   MessageBox.Show(“Tails Up”);
}

Now that’s a pretty trivial program, but if we look closely, we have two states the program can go through, heads or tails up.  In order to test our application, we would need to drop the penny in the sensor in both positions and check the output.

Let’s increase the scope of our trivial application to include that of checking a dime at the same time.  Now the user will drop a dime in the dime reader and a penny in the penny reader.  Our application will tell the user the result.

CoinState pennyState = pennySensor.GetState();
CoinState dimeState = dimeSensor.GetState();

if (pennyState == CoinState.HeadsUp && dimeState == CoinState.HeadsUp)
{
   MessageBox.Show(“both coins are heads up”);
}
else if (pennyState == CoinState.TailsUp && dimeState == CoinState.HeadsUp)
{
   MessageBox.Show(“the penny is tails up and the dime is heads up”);
}
else if (pennyState == CoinState.HeadsUp && dimeState == CoinState.TailsUp)
{
  MessageBox.Show(“the penny is heads up and the dime is tails up”);
}
else if (pennyState == CoinState.TailsUp && dimeState = CoinState.TailsUp)
{
   MessageBox.Show(“both coins are tails up”);
}

You can see now that we’ve increased our number of basic states.  We went from 2 states to 4 by adding the second variable (the dime’s state).

This isn’t really earth shattering, but we can begin to see the correlation between the number of states in the program and the amount of complexity.  In fact, you can generally calculate the number of states using basic math.

Where x is the number of variables, s is the number of states, and t is the number of total states of the program:

t = s^x

As you can see, we are dealing with an exponential problem.

Here are the numbers when dealing with an application made of variables who can have 6 states:

That’s quite a lot of states for a program with only 12 variables.

Managing State and Complexity Through Partitioning

Looking at the chart above, we can generally know that any non-trivial application will have a huge number of possible states.  What can we do about it?

Well, the trick is that while a single program with 4 variables of 6 states will have a total number of just over a thousand states (1296), it doesn’t have to be that way.  Here is where partitioning comes to our rescue.  In fact, if we only create one partition and split the program into two programs, we significantly reduce the number of possible states:

Single Program of 4: 1296 states

Single Program of 2: 36 states
Two Programs of 2 states: 72 states

The reduction is pretty staggering.  We went from 1296 possible states down to only 72!  That’s a reduction of over 94%!

Now if the correlation between the number of states and the amount of complexity holds true, you can just imagine the resulting change to the application.

So what can we take away from this, without trying to calculate the number of states in our applications?

Here’s the generalized principle:

Partitioning is a technique for significantly reducing complexity.

And I’ll create a corollary:

Partitioning an application into Modules is a technique for significantly reducing its complexity.

Now, we know that not all means of partitioning are equal, but I’ll leave that for another post.

If you want a bit more on SIP or the math behind partitioning (as described by Roger Sessions), I would encourage you to take a look at his website.