Organizing the Aggregate: Languages for Spatial Computing

Introduction

Computation has become cheap enough and powerful enough that large numbers of computing devices can be embedded into nearly any aspect of our environment. A widening gap, however, exists between the potential users of embedded systems (biologists, architects, emergency response teams, etc.), and the increasingly complex technology available. Typically, the users know what they want from the aggregate of devices, but the programming or design interfaces that they are presented with operate mainly at the level of individual devices and their interactions. Thus, biologists who want to monitor wildlife with mesh-networked sensors end up having to debug real-time code for parallel algorithms in order to minimize Joules-per-packet, and architects who want to create responsive buildings end up worrying about how to create distributed algorithms to ensure correct time-synchronization across the application modules.

Similar gaps are found in many other areas besides embedded systems. For example:

• •

  Robots are becoming cheaper and more reliable, such that teams of robots can now be used in many more applications. For instance, search-and-rescue workers might use a group of unmanned aerial vehicles to search a wilderness area. These search-and-rescue workers should be able to specify aggregate behaviors like sweep patterns, rather than worry about how to share localization and progress data in order to keep those sweep patterns consistent between robots. Modular and reconfigurable robotic systems have similar issues.

• •

  Reconfigurable computing devices like Field Programmable Gate Arrays (FPGAs) can solve complex problems extremely quickly. Programming and code reuse are difficult, however, because subprograms need to be tuned for their layout on each particular model chip and their context of use relative to other subprograms. Similar issues are likely to emerge in multi-core systems as the number of cores continues to rise.

• •

  In synthetic biology, it will soon be desirable to program engineered biological organisms in terms of the structure of tissues or colonies, and of their interaction patterns, rather than by selecting particular trans-membrane proteins and adjusting their signal dynamics and metabolic interactions. Emerging chemical and nanotechnological computing platforms are likely to face similar issues.

Fundamentally, this gap lies between programming the aggregate and programming the individual (Figure 1). For the users, the application is often best specified in terms of collective behaviors of aggregates of devices. For example, an architect may wish to use sweeping patterns of light on the floor and walls to guide visitors through a building. When implemented on a system of computing devices, however, the application must be carried out through the actions and interactions of many individual devices. For example, a particular LED on the wall must discover whether it is on a visitor's path and then synchronize with its neighbors to ensure that it turns on and off at the correct times to create the desired pattern. Thus, we see that the critical element for bridging the gap between a user and a system of many devices is global-to-local compilation (Abelson et al., 2000), facilitated by the development of a new programming language or languages suited to describing aggregate behaviors.

Figure 1.

A widening gap exists between the application needs of users and the implementation details of those applications on increasingly complex systems of interacting computing devices. This gap must be crossed by global-to-local compilation: the transformation of specifications of aggregate behavior to actions of individual devices.

All of the domains that we have mentioned so far share a property: a close relationship between the computation and the arrangement of the computing devices in space. These systems thus fit the definition of spatial computers-collections of local computational devices distributed through a physical space, in which:

• •

  The difficulty of moving information between any two devices is strongly dependent on the distance between them, and

• •

  The “functional goals” of the system are generally defined in terms of the system's spatial structure.