The Science of Software

This article written by Mike Griffiths was first published by PC Pro magazine in 2001 as “The Science of Software”. This HTML version has additional illustrations and links and has been updated where appropriate.

Are software bugs all the fault of the programmers or could one of the underlying laws of the universe be taking a hand?

There is growing evidence that software and computer systems can appear to think for themselves and evolve new patterns of behaviour never dreamed of by their creators. Usually we dismiss such changes as bugs although sometimes they can be beneficial, enhancing the functionality of a system for it's users. Can software developers devise ways to draw upon the benefits of this behaviour or at the very least come up with new techniques to ensure that our word processing package does not dream up new bugs of it's own?

Imagine pouring grains of sand in a steady stream to form a single pile. The slope of the pile slowly builds until it reaches a point beyond which it will not grow. As further grains are added they slide off the surface of the pile. These slides mostly take the form of small avalanches but there are occasional medium sized slips and more rarely large landslides. It's not possible to predict if the next grain of sand will cause a small, medium or large slide. It does not matter how many sand piles you build in this way, they all exhibit the same fundamental behaviour once the slope of the sand pile reaches a similar critical value. The sand pile is said to be in a Self Organised Critical State.

When Per Bak wrote the paper that first coined the phrase 'Self Organised Criticality' he used this sand pile metaphor and he built a computer model to demonstrate that a landslide that is ten times bigger than the smallest occurs ten times less frequently. If you were to plot how many slides of each magnitude occurred on a logarithmic scale you would get a straight line. He saw that it was impossible to predict the size of the next slide but that you can forecast that a certain number of slides of a given magnitude will occur over time.

The concept of 'Self Organised Criticality' took the scientific world by storm and the sand pile now ranks alongside the proverbial butterfly when coming to grips with complex or chaotic systems. Similar patterns had been observed for earthquakes and statisticians had noticed them when plotting the incidence of such things as population densities, forest fires or even childhood measles. Suddenly it looked as though similar systems could be found everywhere.

What has this to do with software? Well there is growing evidence that software can reach a level of complexity where it's in a state that is analogous to the sand pile. A small change to the code or the operational environment may result in a large change in behaviour. A short while ago I did some consultancy work with a software house that published a package that met the needs of a distinct manufacturing speciality. One of the key programs in the package had been in a state of continuous development for more than two years. There had often been more than one release a week with new features, additional options and, realistically, regular bug fixes. The development team had a problem. They wanted to rewrite the program from scratch but they were aware that their records of changes and development were incomplete and they no longer knew just what the program should be doing. The support team was also convinced that some of the user base were using unintentional features of the program to help manage their businesses. The challenge was to devise a way of building a new program that retained the positive attributes of the current one while dumping as many of the bugs and design limitations as possible. The need to rewrite the program was clear to all as introducing additional features or fixing reported bugs was becoming increasingly difficult - small changes sometimes produced serious glitches in the operation of the program. The software had reached the 'critical slope' of the sand pile and was suspected of harbouring many features that were not part of the design. The software had, to a limited extent perhaps, become self organised.

If the complexity of a software system can reach a stage approaching self organised criticality then this has far reaching implications for the development of safety critical systems everywhere. An apparently stable, tested system could suddenly change it's functionality.

I first became aware of the potential of software to develop new functionality many years ago when I wrote a program that allowed an interactive user to allocate cash to outstanding items on a sales ledger after the automatic processes had failed to do so. It was some months after the installation of the program when I paused to observe 'my baby' at work one day. I watched the operator try a number of strategies and I had just decided that this particular transaction was going nowhere, when with a few deft keystrokes (no GUI in those days) the problem was solved. I was astounded, I had just seen my software do something I knew it could not do. It turned out that one of the operators had 'felt' that a particular approach might work - found it successful and passed the tip on to the others. It took me a long time with the code to spot what was going on. There was, of course, a series of logical 'holes' in the software that had allowed a human operator to join functions together in a way that had not been planned by me, the programmer. While this was not an instance of self organised criticality it did spark an enduring interest in the relationship between the design and behaviour of software systems.

All professional software developers will have come across those talented individuals who write nearly bug free code and also across those who drown in a constant sea of error messages and program terminations. Allowing for the fact that some people code with a great deal more precision than others, the structure of the software could also be playing a part. Adherents of structured programming techniques have always claimed that their methods lead to more accurate coding with fewer bugs. It's probable that they also introduce constraints that limit the potential of a given piece of software to become self organised. Self organisation does not require any sense of purpose or intelligence or any ability to directly control an environment. Self Organisation is inherent within the physical structure of the grains of sand arranged in a pile and could occur just as naturally within a computer system. In most instances the actual code running in a computer will have been compiled and linked to a potentially vast array of external functions. However, the core of any software module will still reflect the structure imposed by it's author. In addition, it runs within a software matrix that is potentially unique on any given machine. This adds to the complexity of the whole and provides further opportunity for self-organisation.

The idea that a process can suddenly appear to develop new behaviour takes a little getting used to. Some readers may be familiar with Langton's ant. If you are not, then let me introduce it to you. It's an interesting demonstration of something called 'Emergent Behaviour'.

Please imagine a large surface made up of square white tiles with an imaginary ant somewhere around the middle. The ant follows two very simple rules. The first rule is, that if the ant is on a white tile it turns it black and then moves one square to the left. The other rule is, if the ant is on a black square it turns it white and moves right. When the ant first starts to move about the surface it appears to move in a fairly random manner. At around 10,000 moves it suddenly switches to a fixed and repetitive pattern of movement from which it will not deviate. The difference is quite startling. Even if the initial 'surface' is seeded with black tiles the same eventual behaviour will emerge although the number of moves will usually be more than 10,000 before this occurs.

Just occasionally, the fixed behaviour of Langton’s Ant is triggered earlier by the initial settings of the ant's world. The rules are straightforward to implement in most programming languages and you can experiment with different starting points. You will find that in all instances the same final fixed pattern will be achieved. The ant performs a repetitive sequence of 104 (in this instance) steps and at the end of each cycle the ant is displaced one tile verticaly and one tile horizontaly. So far, no-one has come up with a mathematical proof that this will always be so but experimental evidence suggests that the proof should be forthcoming one day.

For more on Langton’s Ant and to get your hands on some Visual Basic code to run your own simulation click here.

So now we have a demonstration of apparently random behaviour suddenly changing and becoming seemingly purposeful in a way that would be very difficult to predict based upon the initial movement of the ant or from the simple software that drives it. The process must reach a critical state but instead of triggering chaotic responses following a power law it switched to a fixed behaviour. We could have a software system ticking away quite happily when a particular sequence occurs that triggers the emergence of a new, fixed but unpredictable behaviour.

How does self-organisation relate to chaos theory? Systems that we describe as chaotic have complex behaviour which is built up from a few simple rules. Apparently chaotic systems, from fractals to our weather are based upon simple structures or rules. Self-organised systems, in contrast, evolve within complex structures generating a simple emergent behaviour. The use of computer generated images in films shifted from the rather mundane to the amazingly realistic when it was understood that complex movements and relationships could be built up from simple rules. What started with Craig Reynolds' program "Boids" led to Jurassic Park and beyond.

One avenue of future research may be to harness self-organisation within complex systems to achieve software that remains stable while adapting to changing conditions. Thus we might alow our software to develop using the techniques of “natural selection” but provide elements of an artificial environment that constrain the overall behaviour within certain bounds. perhaps an analagy would be Isaac Asimov’s three (later four) laws of robotics. He alowed his fictional robots to develop beyond the capabilities of their creators but they remained constrained to serve and protect humanity.

Does self-organisation have parallels in natural selection? Well yes and no. Natural selection occurs in a population of organisms where a mutation occurs. If this mutation allows an individual to be more successful when reproducing then, over time, it's likely that the whole population will "adopt" the new characteristic. Self-organised behaviour is governed by a key factor (known as an attractor) that represents a stable state. Natural selection is generally a response to external change and self-organisation is a response to something internal to the system. In nature, it's probable that both self-organisation and natural selection are at work. There is a lot of current research into developing both software and electronic systems using the techniques of natural selection. Initial work on 'boolean networks' of large and randomly connected logic gates (AND, OR, XOR, NOT etc) usually produced unstable systems that rapidly switched between alternate states. Systems that were allowed to change their connections (i.e. allowed to mutate) often developed a stable, self-organised state.

Natural selection has been harnessed by researchers like John Koza (of Stanford University and Genetic Programming Inc) and his work on genetic programming (GP) is now starting to deliver practical designs for devices such as process controllers that outperform the best conceived by human designers. Koza and his team work with a Beowulf style parallel cluster of 70 individual 533-MHz Alpha processors linked by a 100 MBs Ethernet network. They also have a 1,000 node cluster of 350 Mhz Pentium II machines. They would like to take their GP techniques into three dimensional product design but are hampered by a lack of processing power. The solution may be on the way. IBM are constructing a new super computer named Blue Gene and plan to run it for the first time during 2003. This machine will be based upon 1,179,648 processors each running 8 simultaneous threads. Thus over 9 million processes can be harnessed to deliver over 1,000 teraflops  - perhaps the equivalent of over 1 million up-to-date desktop PCs. In fact the design of Blue Gene is generalised and is expected to become the first of a new generation of super-computers designed specifically to manipulate data.

The IBM machine was originally planned to tackle a very complex biological problem. They intend to run a computer model in an attempt to understand how proteins 'fold' into the specific shapes that they do within a tiny time frame and without false steps or paths. As no-one knows how this is done it can't be pre-programmed but it is hoped that the simulation will allow the answer to emerge and explain the self organised final state.

Most of the research into both self-organised systems and emergent behaviour relies upon computer simulation. Now research is also focusing on computer systems and software. The designers of programs intended to act as 'intelligent agents' are building in features that they hope will result in their products developing new, purposeful behaviours to the benefit of their users. Developers working in this field have to accept that frequently their creations fail to achieve the expected results as their software agents just go off and do their own thing. Any computer system or even a single program can be large and very complex. The future will see even more complex systems with software interacting with processes running on servers throughout the world. This is just the situation within which self-organised systems form and we are likely to see new features emerging from the complexity.

Next time a glitch occurs on your computer it might be just the software developing, by itself.

[ Home] [About Us] [Systems] [Software Review]