Project Description
This project explores the use of logic-based multiset rewriting as an
effective approach to programming very large ensembles of distributed agents.
The investigation is carried out in the context of
Claytronics, an
ambitious project to develop programmable matter — cyber-physical
systems of millions of submillimeter scale computing units capable of
executing code, communicating with nearby units and moving around their
neighbors subject to program control and the laws of physics. Other contexts
where this work applies include
micro-economic analysis,
biomolecular simulation,
flow dynamics,
crowd rendering, as well
as the programming of sensor networks, Internet routers, autonomous vehicles,
power management systems, and the specification and verification of
cryptographic protocols.
The project investigates a model of computation based on higher-order multiset
rewrite rules as a programming paradigm for large distributed ensembles. The
core formalism has its foundations in linear logic and combines state
transition systems, logic and process algebra. It natively supports
for concurrency, synchronization, mobile code, non-determinism,
non-monotonicity, and atomicity. The goal of this project is to develop this
base formalism into a strongly-typed declarative programming language, build
an implementation, and use it to program complex behaviors beyond what is
practical in with current languages for Claytronics and other large ensembles.