Firefly

Unfortunately, your browser does not support Java.
A Java applet is the central focus of this page.
You're encouraged to try again using a Java-aware browser.

A version of this applet using Sun's Java plug-in is available here.

Introduction

This applet displays a cellular automata designed to illustrate global synchronous behavior arising in a system based around purely local interactions.

Such systems are commonly known as "firefly" systems after the synchronous flashing of fireflies in some parts of the world.

If the automata above does not appear to be flashing this is due to it being configured to avoid giving users a headache. To observe the flashing, set one of the options to read "Show every frame".

Speed

The automata has a main control with three settings which influence how rapidly it converges to synchronous behavior:
  • Fast but brittle:
    • The automata becomes synchronised as fast as is theoretically possible. Unfortunately, it is very unstable and perturbations may cause very large disturbances, and complete loss of synchrony.
  • Slow and robust:
    • The cells converge to a synchronous state only extremely slowly. However, once a synchronous state has been reached, it is very robust and cannot be easily disturbed.
  • A mixed strategy:
    • The cells are a mixture of the above two types. The properties are also a mixture the automata is much more stable than in the fastest possible automata, and much faster than the most robust automata.

Applications

Perhaps the most significant reason for studying systems exhibiting large-scale global synchronous behavior is their application to the construction of deterministic parallel computers.

The technique which is responsible for maintaining synchrony in most modern desktop computers involve a single point where a crystal generates a periodic signal, which is then magnified and distributed throughout the processing area of the computer.

It should be obvious that such techniques do not scale very well. As the computer increases in size an absolute limit is reached where the clock signal cannot propagate throughout the entire computer before the next pulse is generated. This produces a compromise between the maximum clock speed possible and the radius of the processing components of the computer. There are other problems: the signal decays with distance and must either be amplified or of very variable strength.

Firefly-techniques attain global synchrony from entirely local interactions. They are not subject to the same limitations that conventional clocking techniques impose, and should be capable of maintaining synchronous behavior over a much larger area or volume.

One potential problem with them is that their components are more complex than the simple conductor required by a central propagation technique. This is utterly irrelevant if something as complex as a 32-bit addition is occurring in parallel in every clock cycle - but may become an issue if the computing components of the system become very simple.

Other solutions

One theoretical solution to problems with the centralised approach involves placing the clock source at the centre of a sphere and distributing the components over the sphere's surface. This postpones many of the problems - at least until it becomes necessary to employ three dimensional computing substrates.

Another such possible attempt to fix up the centralised model allows components at different distances from the clock source to respond to the signal in different ways. In other words, components exchange information with neighbouring components 30, 60, 90 degrees out of phase with the main clock signal, at times which depends on their distance from the source of the signal.

This latter approach is a genuine rival to firefly techniques. Which sort of technique is more appropriate depends on engineering considerations.

Remaining questions

Are large synchronous computers actually of any use? For the majority of applications large parallel computers don't need to exhibit large scale synchronous behavior, as the operation of their components need not be completely deterministic to be useful. Other factors, such as the susceptibility of computers with large component counts to point failures, also make building large deterministic computers problematical.

If it is not absolutely essential, using a computer which must be deterministic should be avoided wherever possible. However it seems likely that humanity will continue to find uses for deterministic operation.

The demonstration here is designed to illustrate the idea that the possibility of generating global synchronous behavior through local interactions is of relevance to the clocking of large computers.

Much work needs to be done before it can be said that the concept is properly proven.

The simulation here makes no attempt to simulate a system composed of a network of analogue components with varying response times, in order to illustrate how this might exhibit global synchrony. More complex and realistic simulations are probably the most appropriate next stage in the development of the idea.

The mixed strategy presented here was located by a trial-and-error process. No claim is made about how well it solves the target problem. Exactly what type of firefly system is most appropriate as the basis of a large deterministic computer is still very much an open question.

Lastly, there are questions of power consumption and heat dissipation to be addressed. The 'fast' automata presented here is reversible everywhere, except at its edges. The other automata are not fully reversible - and it appears that if they are to retain the property of being resilient in the face of errors, they cannot be made perfectly reversible. Making a firefly-system with very low power consumption and heat dissipation figures should be possible, however.

Interactive controls

  • Type - controls whether the automata is fast and fragile, slow and robust or a mixture of the two;
  • Tool selection - controls which type of tool to use to manipulate the environment;
  • Tool behavior - controls how the tool in use is applied;
  • Display - controls which aspect of the automata is presented;
  • Resolution - controls how many cells are displayed, and their size;
  • Wrap around - if on the automaton takes on the geometry of a torus;
  • Show frames - configures how frequently the display is updated;
  • Noise level - allows the level of noise present to be controlled;
  • Restart - restarts the automata with the current initial configuration;
  • Clear - completely clears the grid;
  • Step - allows a paused automata to be single-stepped;
  • Pause - allows the automata to be stopped and started;
This applet can also be run as an application. Download this jar file (using shift-click) and double-click on it.

Index | HAL | EoSex | Firefly | CA | Links

tim@tt1.org | http://www.alife.co.uk/