Claytronics is an ongoing project at CMU to develop programmable matter---bringing the power of programming to physical matter. The challenges in realizing Claytronics are all about scaling: (1) scaling the individual units down in size requires novel hardware mechanisms and manufacturing methods, and (2) even more importantly, scaling up---developing an ensemble programming method for millions of units so that they can reliably, even provably, work together to solve a common task. Intel and CMU have already made significant progress on scaling down. In this proposal, we focus on the main challenge of developing a programming language which can scale up in number. We will investigate how MSR (a new approach combining multiset rewriting, logic and process algebra) can form an efficient and flexible basis for programming Claytronics. MSR is ideally suited to program large distributed systems as it natively supports concurrency, synchronization, non-determinism, non-monotonicity, and atomicity. MSR has been used with great success in such diverse areas as security protocols and biomolecular systems. We believe that our investigations will reap rewards beyond Claytronics leading to a basic understanding of how best to program all large ensembles. If successful, we will be able to more efficiently program such diverse systems as sensor networks, Internet routers, autonomous vehicles, and the power-grid.