Conway's Game of Life is a cellular automaton consisting of a 2-dimensional grid of cells each of which is either dead or alive. Each cell undergoes state transitions according to its own state and the states of its eight neighboring cells. When a cell is alive, it remains alive if two or three of its neighboring cells are also alive, otherwise it dies. When a cell is dead, it changes to alive if three of its neighboring cells are alive, otherwise it remains dead. Though an individual cell is quite simple, the aggregate behavior of many cells can be quite complex. For example, the lightweight spaceship is an example of a configuration of cells that essentially moves across the grid.
Although the Game of Life is a synchronous model it can be simulated using an asynchronous model (see, for example, Nehaniv '02 for details). The basic idea is to keep the cells nearly-synchronized at a local level by recording a local time at each cell. The system must ensure that the local times of neighboring cells differ by at most one unit of time. Each cell also records its previous state so that neighboring cells that lag behind a cell can catch-up. This removes the need for a global clock. It also removes the need for any global state – each cell can record its own state and its (most recent) view of the state of its neighboring cells.
The embedded video shows a lightweight spaceship moving across a 14x7 toroidal grid. The black, white and gray cells are alive, dead and recently-dead respectively. The interesting part is how this visualization was generated. The asynchronous transitions were performed using Storm, a distributed and fault-tolerant real-time computation system, running on Amazon Web Services. The definitions for the spout, the component that generates the lightweight spaceship in the first place, and the bolts, the components that perform the transitions and propagate the changes to the neighboring cells, were written using RedStorm. RedStorm integrates JRuby with Storm and provides a DSL for defining spouts and bolts. A subset of the changes were further propagated to Pusher using a Ruby client. A HTML5 application subscribed to these updates using Pusher's JavaScript client. It rendered the grid using a HTML5 Canvas and Backbone.js and updated the cells as necessary.
The code for the Storm topology is available on GitHub.
