On inventing laws of nature, faking intelligence, and understanding time
Tarek Abdelzaher
With advances in hardware, radio communication, and
batteries, it is now possible to make miniature devices as
powerful as early PCs. These communicative devices can talk
with each other, sense their environment, record sounds, measure
temperatures, and perform a myriad of small, simple tasks.
Collectively, these "smart" devices can perform large,
complicated tasks, and they are getting smaller and smaller,
approaching the "smart dust" level. Besides their obvious
military and surveillance implications, what else can we do with
them? Abdelzaher has more than a few ideas, some of which he is
implementing with his sensor networks group. "Using sensor
networks, we can learn things at a fine grain, especially about
nature," he said.
Sensor networks: As smart as an ant colony
Large sensor networks challenge traditional models of computation, which are based on the notion of centralized PCs or large machines. A sensor network comprises many individually insignificant and unreliable entities yet exhibits a collective, predictable behavior. The fundamental challenge for researchers like Abdelzaher is learning how to design programs for these networks.
"We don't want to program each particle individually," said Abdelzaher. "Instead, we need a higher abstraction level or a compiler smart enough to translate from a high-level language to the level of telling each particle what to do and how to coordinate with the other particles."
Abdelzaher derives his inspiration from chemistry, physics, and biology, particularly from distributed intelligence among animals. "An individual ant does not realize what's going on in its colony, yet some collective behavior emerges from the individual behavior of all the ants," he said. "But what exactly does an individual ant know? What is its local response to stimuli? What is the simplest rule that would lead an ant to keep its nest clean? It turns out that very trivial rules will do. When thousands of ants implement the same rule, it leads to sophisticated intelligent behavior, or at least the appearance of it." Copying nature promised to lead to the best way to solve complicated problems with particles and communities of particles working together. After all, creatures have found natural solutions arrived at over millions of years of evolution. Digital computers have been around for less than a century.
Biologists have observed this phenomenon in social insects and individual cell growth. "They do this predictably," he said, referring to a cell, which obeys only a limited set of chemical reactions. "These few rules together generate extremely complex beings." For this reason, Abdelzaher thinks it is possible to build simple, primitive devices with finite storage capacity to do extremely complex and sophisticated tasks, when assembled in large masses, if only we better understood the principles behind collective behavior in biology. The same notion applies to physics and chemistry: Taking a microscopic view of a material, the atoms and molecules differ in number, orientation, and alignment, yet taken together, they behave in a predictable and reliable way as an aggregate. Steel behaves like steel. Glass behaves like glass."
Abdelzaher is trying to do just that with sensor networks: Build predicable aggregate behavior from a network of sensors, each of which individually is pretty simple. "In a sense, we get to play god," he said, "because you cannot change the instinct of an ant, but you can reprogram a particle. The question is, what little rules of nature should we invent for the individual particles so that we get the behavior of choice out of the collective?" In a sense, this is the reverse of the problem faced by biologists. "Their rules of nature are just there." In biology, one needs to understand primarily how rules of nature lead to phenomena we observe. In sensor networks, we get to create the rules that lead to customized phenomena we specify.
It took several decades of research to understand how to build and standardize protocols that keep the Internet running smoothly. Sensor networks are on the wild and wooly frontier, whose protocols are in their infancy. What would the equivalent of IP on the Internet be in a sensor network? A critical part of Abdelzaher's research involves developing network architectures, protocols that govern communication between particles, and eventually a high-level language for sensor networks. "It is our responsibility, on the university side, to demonstrate which particular protocols work well so they may be adopted by the larger community and perhaps standardized."
Abdelzaher's interest in sensor networks has led to some interesting collaborations with other researchers on campus. Testbeds with environmental monitoring equipment are located in the vicinity around the campus in which Abdelzaher has deployed his protocols. In one project, his sensors measure vocalization of birds at night to help understand their social behavior. Equipped with simple microphones, his network is able to tell what kind of chirp was made, where the chirp took place, and so forth. His sensor network also knows which chirps are unique (e.g., when more than one sensor records the same chirp). Abdelzaher hopes to track sensors located on animals-even grasshoppers-containing oscillating crystals detectable as far as 50 meters away. Currently, monitoring insects is very labor-intensive, intrusive, and only a few at a time can be tracked.
Abdelzaher is also exploring embedded sensors in clothing,
which can be used for a variety of purposes from monitoring an
elderly person living alone to finding interesting statistics on
the behavior of masses of people to a second-by-second
reconstruction of someone's life. Imagine an obesity study
conducted by subscribing to a website that allows data from your
smart refrigerator and weight-detecting shoes to be anonymously
shared in exchange for statistics on diets and their effects
measured from the subscriber community as a whole.
Real-time systems: Time-critical tasks that go with the flow
Abdelzaher's real-time systems work is motivated by his sensor network work. Most real-time systems research has been on large computers, like the central control of the space shuttle. Abdelzaher is concerned with large collections of individual machines that work in concert as a system in which the timing of events is critical. The challenge is to predict and control timing behavior in this type of environment. This is very different from the traditional scheduling problem involving one machine with its processors taking turns doing tasks according to schedules and priorities. In a sensor network, lots of little computing particles are collaborating on one task, as opposed to one machine juggling several tasks concurrently. The multitude of tasks moving from stage to stage is akin to a liquid flow. "There is no good theory on how much you can put into the flow and how soon it will get done. The tradeoff between how much can be done and how fast it can be done has not been evaluated in this context," he said.
To illustrate the flow concept, Abdelzaher pointed to Google, which maintains thousands of machines in its server farm. Every search request flows through its system by touching hundreds of machines, and the user can read the response time (in fractions of a second), in addition to the number of hits, on the screen after the search turns up its results. According to Tarek, Google over-provisions by buying lots of hardware, without a fundamental theory for computing the real limitations and capabilities of the system. To understand the tradeoff between volume and speed, they simply test. "They buy a lot of cheap PCs and split up the computations into as many pieces as they can, with 40 to 50 stages of processing per request. Different parts of the Web sit in different parts of the farm. The results from each part are concatenated together and served to the user." Energy becomes a huge problem. Google could benefit from a system that dynamically adapts to its load to conserve energy. They want to put as many machines to sleep as possible when not needed. The problem is, to understand how many machines can be safely put to sleep one must understand how speed and volume are related.
When a system is poorly understood, but you want it to behave predictably, one option is to use feedback control. That is to say, you measure something (e.g., requests), and then control something (e.g., number of machines that are asleep). This feedback control loop is the foundation of control theory. A thermostat in a refrigerator is a good example. It will maintain a certain temperature inside without caring about what the weather outside is doing because its thermostat is set to that temperature. "If we could do this with a computer system," said Abdelzaher, "it would be great. I want to use principles of feedback control to create predictable behavior of software without having to know much about its internals."
One way Google could predict what the delay would be if
they turned off a few servers is to build a mathematical model
of their system, apply techniques from queuing theory to describe
the system, analyze the model, and infer what the system should
do to behave well. But using such theories requires making
assumptions, and if too many are made, the system becomes
brittle. Instead, Abdelzaher would like to know if the system
will behave well without building a model and how much he can get
away with without knowing.
Written by Judy Tolliver,
April 10, 2006
--
Last Modified August 07 2006 09:03:03.
