{"id":1020,"date":"2024-03-29T10:15:10","date_gmt":"2024-03-29T17:15:10","guid":{"rendered":"https:\/\/labs.engineering.asu.edu\/sops\/?page_id=1020"},"modified":"2024-03-29T10:17:11","modified_gmt":"2024-03-29T17:17:11","slug":"amoebot","status":"publish","type":"page","link":"https:\/\/labs.engineering.asu.edu\/sops\/amoebot\/","title":{"rendered":"Computing by Programmable Particles"},"content":{"rendered":"\n
<\/div>\n\n\n\n
\n
\n

Joshua J. Daymude, Kristian Hinnenthal, Andr\u00e9a W. Richa, and Christian Scheideler.[PDF<\/a>] [Springer<\/a>] \u2014 Book chapter in Distributed Computing by Mobile Entities<\/em>, pp. 615\u2013681, 2019.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Overview<\/h2>\n\n\n\n

The vision for programmable matter<\/em> is to realize a physical substance that is scalable, versatile, instantly reconfigurable, safe to handle, and robust to failures. Programmable matter could be deployed in a variety of domain spaces to address a wide gamut of problems, including applications in construction, environmental science, synthetic biology, and space exploration. However, there are considerable engineering and computational challenges that must be overcome before such a system could be implemented. Towards developing efficient algorithms for novel programmable matter behaviors, the amoebot model<\/strong> for self-organizing particle systems and its variant, hybrid programmable matter<\/strong>, provide formal computational frameworks that facilitate rigorous algorithmic research.<\/p>\n\n\n\n

This chapter is a recapitulation of the first four years of theoretical research on the amoebot model. We begin with a fully detailed definition of the amoebot model, differentiating between what we see as core model features versus model extensions. We then describe three algorithmic primitives:<\/p>\n\n\n\n

    \n
  1. Leader election<\/strong>. How can anonymous, local, distributed particles elect a unique leader?<\/li>\n\n\n\n
  2. Spanning forest primitive<\/strong>. How can a particle system organize and move along a specified path?<\/li>\n\n\n\n
  3. Distributed binary counters<\/strong>. How can a particle system store values that are too big for any one particle\u2019s memory?<\/li>\n<\/ol>\n\n\n\n

    These primitives are useful components of more complex algorithms, including shape formation<\/strong>, shape recognition<\/strong>, object coating<\/strong>, compression<\/strong>, shortcut bridging<\/strong>, and separation<\/strong>. We describe each of these algorithms in detail (including many new figures) and give the highlights of their theoretical analysis (including correctness and runtime bounds).<\/p>\n<\/div>\n\n\n\n

    <\/div>\n<\/div>\n\n\n\n
    <\/div>\n\n\n\n
    \n
    \n

    Resources<\/h2>\n\n\n\n