Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

1.4 CELLULAR AUTOMATA AS MODELS FOR FLUID FLOW

1.4.1 Introduction

Section 1.2 introduced the basic idea behind CA and explained how one can reason about information and complexity in general CAs. Here we introduce a very specific CA, which, as will become clear later on, can be used as a model of fluid flow. This class of CA is called lattice gas automata (LGA), and is described in detail in two recent books [11, 58].

Suppose that the state of a cell is determined by b_m surrounding cells. Usually, only the nearest and next-nearest neighbors are considered. For example, on a square lattice with only nearest-neighbor interactions b_m = 4, if next-nearest neighbors are also included, b_m = 8, and on a hexagonal lattice with nearest neighbor interactions, b_m = 6. Furthermore, suppose that the state of the cell is a vector n of b = b_m bits. Each element of the state vector is associated with a direction on the CA lattice. For example, in the case of a square grid with only nearest-neighbor interactions we can associate the first element of the state vector with the north direction, the second with east. the third with south, and the fourth with west. With these definitions we construct the following CA rule (called the LGA rule), which consists of two sequential steps:

1. Each bit in the state vector is moved in its associated direction (in the example, the bit in element 1 is therefore moved to the neighboring cell in the north) and placed in the state vector of the associated neighboring ...