1. INTRODUCTION

This is additional documentation for the sandpile simulation program. 
This document describes the theory behind how the sandpile works. 
You don't need it to run the program, but you might find it interesting, 
never the less. For information on how the program works, see the 
file manual.doc.

The background story is that in '95 a fellow student and I wrote a 
report about self-organized criticality (SOC). SOC systems are 
systems that reorganize themselves depending on what their 
environment is like. If you are familiar with Conway's "Game of Life" 
you already know a simple SOC system. (SOC systems are also 
known under many other names, like "dynamic", "self-organizing", or 
"complex adaptive" systems).

We found SOC systems to be rather fascinating, so I've decided to 
publish a resume of our report, which is the document you are 
currently reading. As an example of a SOC system we made a 
sandpile simulation for DOS. Now I've modified it for Win95, and 
the source code is published as freeware for your convenience.

Please note that although I believe what this document says about 
SOC theory and sandpiles is valid, I don't guarantee it 100%. Our 
sandpile project was, after all, merely chosen as a subject for a 
report in a single-semester course in programming. Besides, I'm not 
studying mathematics or physics, but economy. Also, please don't 
blame me if the simulation program messes up your computer 
(although I would like to hear about it). You carry any risks yourself 
when using the program.

The rest of this document will explain SOC systems and sandpile 
models in more detail. Also, the close relation between SOC and 
chaos will be explained.

2. THEORETICAL BACKGROUND

I'm not quite sure of it, but I think Per Bak et. al. should have the 
credits for publishing the first article on sandpile models in 1987. 
Whether it's true or not, this article made sandpile models very 
popular.

The term "sandpile model" refers to a relatively simple model, that 
loosely resembles how a real-life sandpile behaves when you add 
grains onto it. The pile will grow higher, but at the same time the 
grains you add will fall down the sides of the pile, causing more grains 
to fall down, etc. The idea is that you can't tell exactly when a grain 
will fall down and when it will remain where it was dropped. 
However, you can derive some general rules that will apply to the 
pile as a whole (an average view, if you prefer).

The growing sandpile behaves in a certain way, based on rules from 
SOC theory. Our purpose of simulating a sandpile was not to make a 
realistic model of a real sandpile, but to make a model that can be 
used to illustrate this theory.

2.1 Informal explanation of a sandpile model

Think of an ordinary pile of sand. You start with an empty surface, 
and by dropping 1 sand grain at a time (in the same point or in 
random points) the pile will grow steadily. The interesting thing is how 
the pile behaves when it grows. Every time a new grain is added in a 
point the pile may grow unstable in that point. The higher the point is 
situated relative to the neighboring points, the more unstable the point 
will become.

If the point becomes sufficiently unstable a number of grains will fall 
off the point and onto the neighboring points. This will increase the 
neighbors' unstability, and it is possible that more grains will fall 
down. It is also possible that the grains will just stop falling.
Sometimes, the one grain that was added from the start will cause 
entire avalanches, at other times, the pile will not change at all except 
in that one point. The theory that explains why the pile behaves like it 
does, is explained below.

2.2 A theoretical explanation

As mentioned earlier, our sandpile model is a SOC system. For that 
reason I will first explain the theory of SOC systems, before 
explaining the theory of sandpile models.

2.2.1 SOC systems

SOC systems have close relations to chaotic systems, but they differ 
in that SOC systems are less chaotic.

Let's first look at chaotic systems. A chaotic system is defined in 
physics science as a dynamic system (a system that develops). 
Furthermore, the system's future state cannot be predicted with 
certainty, because the starting conditions and the rules of the 
dynamics cannot be determined with sufficient accuracy.

Allthough the starting conditions can't be determined accurately they 
will still influence how the system develops. This means that a small 
initial uncertainty grows exponentially as the system changes (for 
example over time). This in turn means that the more accurate you 
want the predictions on the system to be, the more information about 
the starting conditions and rules you need. The amount of information 
needed grows exponentially, and this often makes long-term 
predictions virtually impossible, as you just can't collect enough 
information.

In SOC systems, on the other hand, the inaccuracy of the predictions 
does not grow by an exponential law, but much slower, by a power 
law. SOC systems, as opposed to chaotic systems, have the ability 
to adjust themselves, which means that they develop on the border of 
chaos. Per Bak et. al calls this "weak chaos".

Simply spoken, the special attribute of a SOC system is that as it 
develops it organizes itself around a critical factor. If the state of an 
element in the system reaches a critical value the element will change 
its state, which in turn often will influence the state of other elements. 
One or more elements may trigger a chain reaction. After the 
elements have settled in their new state, the system is organized in a 
new way.

This is illustrated by the sandpile model. A sandpile is a dynamic 
system where many elements interact with each other. The system 
(sandpile) will at some time in its development reach and exceed a 
critical value (it will become too high or steep). A change in a system 
with a critical value (in the form of an added sand grain) may at this 
time trigger chain reactions (avalanches) which will influence the state 
of the system (the height of the various points).

2.2.2 Types of sandpile models

There are 3 main groups of sandpile models:
  Critical height model
  Critical slope model
  Critical Laplacian model

Each group of models builds on different interpretations of the local 
height function h(x,y).

The critical height model is the one we used in our project, and we 
based it on a 2D-matrix. Each point (x,y) in the matrix has a value 
h(x,y) which represents the height. If this height at any time exceeds 4 
the point will topple. This is done in the way that the height in the 
neighbor points to the north (x, y-1), south (x, y+1), east (x+1, y), 
and west (x-1, y) each are increased by 1, while the heght in (x,y) is 
decreased by 4.

The advantage of changing only these four neighbors is that it won't 
matter in which sequence you change them. This is not the case if you 
change all eight neighbors. Sandpile models in which you change only 
the four neighbors are called abelian (or commutative (?) ), and they 
make the simulation a lot easier. The abelian method is not limited to 
the critical height model, it can also be used in the two other kinds of 
models. There are other methods for updating the neighbors than the 
abelian method. However, it is often the preferred choice, for 
reasons of simplicity.

The sandgrains in this simple model can actually fall uphill. This is not 
realistic, of course, if you want the model to behave like a real 
sandpile, but that was not our purpose. Besides, the SOC principles 
are still valid.

The critical slope model more realistically resembles a real-life 
sandpile. In this model you consider the local slopes (a slope is the 
height of a point compared to its neighbor points). If a local slope 
exceeds the critical slope value in any direction, the point topples. 
Avalanches based on this model don't seem to follow a power law.

The critical Laplacian model is based on a third way of calculating 
the height. This is called the local Laplacian L(x,y), and it's calculated 
as the average difference in height to all neighbor points. The formula 
is: L(x,y) = 4h(x,y)-h(x+1,y)-h(x,y+1)-h(x-1,y)-h(x,y-1). Like 
critical height model sandpiles, avalanches in Laplacian model 
sandpiles follow a power law, but with other exponents.

2.3 A word on cellular automata

To describe the principles in a sandpile there is a certain model that is 
useful. This is the cellular automaton model, introduced by von 
Neumann.

A cellular automaton represents a closed system where the elements 
of the system (called cells) are organized in a structure (a 2-
dimensional matrix, for example). The cells are represented as 
variables (or groups of variables) with discrete values. The state of 
the cellular automaton is determined entirely from the values in each 
cell.

The system is dynamic (it develops over time). The values of each 
cell are updated depending on two factors: 1) the local environment 
(the values in each of the neighboring cells in the previous time unit), 
and 2) a local set of rules. All cells in the automaton are updated 
simultaneously.

A lot of systems in real life can be modelled by the cellular automaton 
model. In physics especially, there are many problems that contain 
many discrete elements with local interactions (eg. the molecules in a 
crystal). There even exists parallel computer architectures based on 
these principles.

You may already know Conway's "Game of Life", which is an 
excellent example of a simple cellular automaton (and at the same 
time a SOC system). In this game each cell in a grid arranges itself 
based on how its eight neighbor cells are arranged. The system 
interacts with itself, but in time it finds a critical state from which 
it won't change unless the cells are changed from outside the system.

Our sandpile is modelled as a cellular automaton. The model is dynamic, 
and the dynamics is based on two factors: 1) the environment (neighbor 
cells), and 2) a local set of rules, which in this case is the same in 
the whole system (all cells). Also, all grains (cells) are updated 
simultaneously (in the same round). So, as you can see, the underlying 
principles for our sandpile model and the "Game of Life" are exactly the 
same.

3. RESULTS OF THE SIMULATION

It is possible to create a number of rules and formulas for the 
behaviour and attributes of a sandpile model, but I will mention just 
one, which is chained to the execution time of the simulation.

The size of an avalanche, s, can vary significantly over time, but the 
distribution of the avalanche sizes can be expected to follow a 
power law (except probably when the sandpile is modelled with the 
Laplacian approach). In other words: s increases with a power 
exponent relative to the number of acumulated grains. Which, in 
english, means: the more grains you add, the bigger the avalanches 
will get - on average. This is hardly surprising.

The formula for the distribution of s is: D(s) ~ s^(1-t), where t 
represents an exponent of size (?), which you can estimate. The size 
of t will depend on the rules of the sandpile model you construct.

Among the factors which influence the dynamics of the sandpile are: 
the size of the pile, its initial state, the rules which determine when 
to topple, and the size of the introduced pertubation (the number of 
grains added at any one time).

One of our goals with our program was to verify that the simulation 
follows a power law in execution time and the size of the avalanches. 
By running a number of simulations and using the above-mentioned 
formula, we estimated t to be approx. 1.491. We did this by letting 
the program generate test-results during the simulations (containing 
the size of avalanches relative to the total number of grains). The 
results were processed in the Excel spreadsheet.

If you like, you can see if you get the same result (you ought to, 
unless I unintentionally changed the program after we ran the 
simulations). The source code of the program includes a tailored log 
object, which has been disabled for purposes of speed. You only 
need to un-comment the object in the main simulation loop (see file 
sandsim.pas).

By the way, the formula is only valid, as long as the surface area is 
big enough to hold all sand grains. When they begin falling over the 
edges, D(s) will be more linear over time, as the lost grains cannot 
start or be part of a chain reaction.

4. CONCLUSION

The SOC theory provides rules for how large, complex, interacting 
systems over time organize themselves around one or more critical 
factors in the system. Our sandpile model was a simple example of 
that.

In real life there are many examples of these large, complex, 
interacting systems - like the stock market, eco-systems, traffic, or 
the weather. Systems like these are quite robust, but every now and 
then they can collapse with just a little outside influence (a bit scary, 
huh?). Keep in mind, though, that systems like these are not closed 
systems, unlike the sandpile model. It is possible to adjust the 
systems somewhat from outside to prevent them from collapsing (the 
opposite is also possible).

Somewhere, I once read a suggestion to why the dinosaurs grew 
extinct. The suggestion involved elements of SOC theory, and I guess 
it went something like this: The entire dino population (or the eco-
system) had organized itself around some unknown factors (maybe 
the relationship between herbivores and carnivores, or other 
"demographic" factors), so the dino population depended on these 
factors. Some outside condition, which might have been insignificant, 
had the system been in another state, was introduced, and WHAMMO! 
The system avalanched itself into destruction. So it didn't have to be 
a doomsday meteorite - it could have been just a bad case of the dino 
flu. Over millions of years the system had worked itself into a critical 
state from where it could virtually destroy itself without much effort.

You see it all the time in nature: if the eco-system is disturbed 
somewhere, the whole system feels the effects. Like avalanches in a 
sandpile, these effects can be of varying size. Eventually, a new 
balance will be established in the eco-system. That just didn't happen 
in the case of the dinos. 

Personally, I kind of like this suggestion. It has some implications that 
make you think.

This concludes what I want to say about sandpiles. Perhaps you find 
sandpiles and SOC systems to be fascinating, perhaps not. If you 
want to go further, I've included a few references that might be useful 
(be aware that most of them are pretty technical - and probably a bit old 
by now). Also, try searching the Internet using keywords like "self-
organized criticality" and "complex [adaptive] systems" - theres loads 
of stuff out there.

Any comments, questions, suggestions, corrections, or the like are 
very welcome.


Troels Jakobsen
tjak@get2net.dk



References

1. Per Bak + Kan Chen: "Self-Organized Criticality", Scientific 
American, Jan 1991. (This is a good article on SOC - interesting 
and relatively easy)
 
2. Per Bak + Kan Chen + Michael Creutz: "Self-Organized 
Criticality in the 'Game of Life'", Nature, vol 342, Dec 14 
1989. (More about cellular automatons, the Game of Life, and 
sandpiles - a short and rather technical article)
 
3. Per Bak + Chao Tang + Kurt Wiesenfeld: "Self-Organized 
Criticality: An Explanation of 1/f Noise", Physical Review 
Letters, vol 59:4, July 27 1987. (A rather technical article of a 
SOC phenomenon known as flicker noise)
 
4. Per Bak + Chao Tang + Kurt Wiesenfeld: "Self-Organized 
Criticality", The American Physical Society, vol 38:1, July 1 
1988. (More about flicker noise in 1-, 2-, and 3-dimensional 
sandpile models - technical but thorough)
 
5. Steven A. Janowsky + Claude A. Laberge: "Exact solutions for 
a mean-field Abelian Sandpile", Working papers - Rutgers 
University, June 1993. (Found somewhere on the Internet)
 
6. Yu Feng + Heather J. Ruskin: "Large scale Simulation and 
Applications", Working papers - Dublin University, June 1994. 
(Found somewhere on the Internet)
 
7. V. B. Priezzhev + D. V. Ktitarev + E. V. Ivashkevich: 
"Formation of Avalanches and Critical exponents in Abelian 
Sandpile Model", Working paper - Joint Institute of Nuclear 
Research, 1980 (?). (Found somewhere on the Internet)
