Printable Version of this PageHome PageRecent ChangesSearchSign In
We've all heard of of ubiquitous computing - wherein computers, display and input devices are embedded into the everyday environment. From the Wikipedia: it "is a post-desktop model of human-computer interaction in which information processing has been thoroughly integrated into everyday objects and activities." Cell phones, pdas, gps watches, ambient temperature orbs, bus arrival prediction signs, etc., are all elements of this kind of interaction.

Well, this thesis takes that concept, smashes all the computers into tiny little fragments, and spreads the dust all over walls, tables, books and cookie jars. The major enabling factor is that ongoing chip process technology will enable the production of autonomous sand grain-sized computing elements that can be obtained and manipulated by the jar full. Imagine 8-pin surface mount chips today; one can carry about 1,000 in a palm, but they still require precise connections to power, sensors, actuators, and other components.

Imagine then, a tiny piece of engineered silicon equipped with wireless tranceiver, program memory, and a way to harvest power parasitically (e.g. solar, ambient RF, heat). Take a few hundred thousand of these chips and suspend them in a viscous medium like paint and spread them over a desktop (or kitchen cabinet, or business card). Expose the surface to power and the chips boot, self-organize, and collectively become a "computer". It shouldn't matter that you take a saw and cut the table in half... now you just have two smaller computers (even if some chips were damaged in the process). The chips might have touch sensors and a single multi-color LED, so you can dedicate an arbitrary section of your table to input, and another to display. Although currently impractical (for purely economic reasons, I think), paintable computers are certainly within reach of today's technology.

The major contribution of this thesis is really how to organize and program these pieces to do things that we find useful. Contraints on the computational model are:
  • Each piece is pseudo randomly positioned
  • The surface can have an arbitrary topology
  • Each piece communicates locally with immediate neighbors
  • The system is extremely fault tolerant (nodes are expected to fail)
  • Clock-level and event-level synchrony is out (code cannot depend on other particles states)

The programming model in this work is therefore based on process self-assembly, where a program assembles itself from randomly distributed fragments of code resident in different particles. Each fragment (pfrag) "signals via broadcast through a medium which supports probabilistic reception over a local area. Data exchanged between proximal pfrags is used to emulate the processes of thermodynamic and scaffolded self assembly."
The approach applies a novel abstraction for inter-process communication which provides support for a pfrag's mobility, replication, scheduling and data exchange.

I'll briefly mention one example application provided in this paper, the others also make for some exciting reading. The "Gradient" process fragment radiates a gradient feild outward from an anchor point. The gradient pfrag from any one particle can copy itself to another particle, increasing the hop count of the new copy. There are rules that govern if a new pfrag could replace an existing one, or if it should automatically remove itself (leaving the particle empty). If the hop count was represented as some color (e.g. red or blue), and particles initially randomly choose one color or the other, one can imagine a table top containing transient (and over time), stable patterns.

The paintable computer (simulated on a standard computer), was also demonstrated to stream audio, act as holistic data storage (i.e. collectively hold and show a complete picture), act as a surface bus for randomly placed PDAs and cameras, and an image segmentor. Pretty cool stuff for a random collection of dust particles.

Last modified 2 December 2007 at 4:42 pm by nwanua