Carnegie Mellon University in Qatar
School of Computer Science, Carnegie Mellon University
Supported by the Qatar National Research Fund


Rewriting Intensive Parallel Programming for Large Ensembles

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.
This work was funded by the Qatar National Research Fund as project NPRP 09-667-1-100 (Effective Programming for Large Distributed Ensembles) for an amount of $1,035,164 over 3 years.



Past members


2014 2013 2012 2011
2014 2013 2012 2010

Multiset Rewriting for Ensembles — MSR(e)

MSR(e) is a high-level declarative distributed programming language based on higher-order multiset rewriting. It provides simple and effective support for programming a large number of interacting nodes as a single entity — an ensemble.

Meld — a High-Level Language for Ensembles Programming

Meld is an extension of the Datalog logic programming language to program ensembles of cyber-physical entities in the style of Claytronics. This part of the project adapts it to support the implementation of distributed algorithms on multi-core architectures.

Related Work