Smart Dust is a set of a vast number of ultra-small fully
autonomous computing and communication devices, with very restricted
energy and computing capabilities, that co-operate to quickly and efficiently
accomplish a large sensing task.
Smart Dust can be very useful in practice
i.e. in the local detection of a remote crucial event and
the propagation of data reporting its realization.
In this work we make an effort towards the research on smart dust
from a basic algorithmic point of view.
We first provide a simple but realistic model for smart dust
and present an interesting problem, which is how to propagate efficiently
information on an event detected locally.
Then we present smart dust protocols for local detection
and propagation that are simple enough to be implemented
on real smart dust systems, and perform, under some simplifying assumptions,
a rigorous average case analysis of their efficiency and energy consumption
(and their interplay).
This analysis leads to concrete results showing that our protocols
are very efficient.