Project: SOPS
We investigate the capabilities and properties of distributed systems that consist of myriads of simple computational particles. These particle systems are able to self-organize in order to solve their designated tasks without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and forming nano-scale devices for surgery and molecular-scale electronic structures. The notion of programmable matter is tightly interwoven with the term self-organizing particle systems, which has the ability to change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion.
The Amoebot Model. Our work aims to build a theoretical foundation for self-organizing particle systems that allows rigorous algorithmic research. To this end, we proposed the amoebot model for self-organizing particle systems in 2014 as a framework that captures many underlying assumptions and physical properties of particle systems in general. We’ve since used the amoebot model to develop provably efficient algorithms for behaviors such as shape formation, coating, and leader election. A detailed description of the model can be found here.
Publications
Book Chapters
- Computing by Programmable Particles. Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa, and Christian Scheideler. In Distributed Computing by Mobile Entities, pp. 615–681, 2019.
Refereed Journal Papers
- On the runtime of universal coating for programmable matter. Joshua J. Daymude, Zahra Derakhshandeh, Robert Gmyr, Alexandra Porter, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Natural Computing 17(1) pp. 81-96, 2018. [Full Text]
- Universal coating for programmable matter. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Theoretical Computer Science, pp. 671:56-68, 2017.
Refereed Conference Proceedings
- Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems. Joshua Daymude, Andrea Richa, Christian Scheideler. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Links pending.
- The Canonical Amoebot Model: Algorithms and Concurrency Control. Joshua J. Daymude, Andréa W. Richa, Christian Scheideler. In The 35th International Symposium on Distributed Computing (DISC 2021), pp. 20:1-20:19, 2021.
- Deadlock and Noise in Self-Organized Aggregation Without Computation. Joshua J. Daymude, Noble C. Harasha, Andréa W. Richa, Ryan Yiu. In the International Symposium on Stabilizing, Safety, and Security of Distributed Systems (SSS 2021), pp. 51-65, 2021.
- Bio-Inspired Energy Distribution for Programmable Matter. Joshua J. Daymude, Andréa W. Richa, and Jamison W. Weber. In the 22nd International Conference on Distributed Computing and Networking (ICDCN 2021), 2021.
- Convex Hull Formation for Programmable Matter. Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Sheideler, and Andréa W. Richa. In Proceedings of the 21st International Conference on Distributed Computing and Networking (ICDCN 2020), pp. 2:1-2:10, 2020.
- Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly. John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine, Matthew J. Patitz, and Andréa W. Richa. In DNA and Molecular Computing — 25th International Conference (DNA25), pp. 140-158, 2019.
- Collaborative computation in self-organizing particle systems. Alexandra Porter and Andréa W. Richa. In Unconventional Computation and Natural Computation – 17th International Conference (UCNC ’18), pp. 188-203, 2018.
- Improved leader election for self-organizing programmable matter. Joshua J. Daymude, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. In Algorithms for Sensor Systems (ALGOSENSORS ’17), pp. 127-140, 2017.
- On the runtime of universal coating for programmable matter. Zahra Derakhshandeh, Robert Gmyr, Alexandra Porter, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. In DNA Computing and Molecular Programming – 22nd International Conference (DNA22), pp. 148-164, 2016.
- Universal shape formation for programmable matter. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’16), pp. 289-299, 2016.
- An algorithmic framework for shape formation problems in self-organizing particle systems. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. In Proceedings of the Second Annual International Conference on Nanoscale Computing and Communication (NANOCOM ’15), pp. 21:1-21:2, 2015. [Simulation]
- Leader election and shape formation with self-organizing programmable matter. Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, and Christian Scheideler. In DNA Computing and Molecular Programming – 21st International Conference (DNA21), pp. 117-132, 2015.
- Brief announcement: On the feasibility of leader election and shape formation with self-organizing programmable matter. Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, and Christian Scheideler. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC ’15), pp. 67-69, 2015.
- Brief announcement: amoebot – a new model for programmable matter. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’14), pp. 220-222, 2014.
Other Publications
- Algorithmic Foundations of Programmable Matter Dagstuhl Seminar 16271. Sándor P. Fekete, Andréa W. Richa, Kay Römer, and Christian Scheideler. In SIGACT News, pp. 48(2):87-94, 2017.
- Infinite object coating in the amoebot model. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann, and Shimrit Tzur-David. CoRR, abs/1411.2356, 2014. [Simulation]
- Ameba-inspired self-organizing particle systems. Shlomi Dolev, Robert Gmyr, Andréa W. Richa, and Christian Scheideler. CoRR, abs/1307.4259, 2013. Workshop paper at Biological Distributed Algorithms (BDA ’13).
Presentations
Invited Talks
- Algorithmic Programmable Matter. Andréa W. Richa. Keynote talk at 22nd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS ’20), Austin, TX, USA (Virtual Event). November 18, 2020. [Video]
- Algorithmic Foundations of Programmable Matter. Andréa W. Richa. Keynote talk at International Conference on Distributed Computing and Networking 2020 (ICDCN ’20), Kolkata, India. January 6, 2020.
- Self-Organizing Particle Systems: an Algorithmic Approach to Programmable Matter. Joshua J. Daymude. 2nd Workshop on Self-Organization in Swarm of Robots (WSSR ’18), Tokyo, Japan. November 4, 2018.
- Algorithmic Foundations of Programmable Matter. Andréa W. Richa. Keynote talk at Latin American Theoretical Informatics 2018 (LATIN ’18), Buenos Aires, Argentina. April 17, 2018.
Conference Talks
- Bio-Inspired Energy Distribution for Programmable Matter. Joshua J. Daymude and Jamison W. Weber. International Conference on Distributed Computing and Networking 2021 (ICDCN ’21), Nara, Japan (Virtual Event). January 6, 2021. [Video]On the Runtime of Universal Coating for Programmable Matter. Christian Scheideler. DNA Computing and Molecular Programming – 22nd International Conference (DNA22), Munich, Germany. September 8, 2016.An Algorithmic Framework for Shape Formation Problems in Self-Organizing Particle Systems. Zahra Derakhshandeh. 2nd ACM International Conference on Nancoscale Computing and Communication (NANOCOM ’15), Boston, MA, USA. September 22, 2015.Leader Election and Shape Formation with Self-Organizing Programmable Matter. Thim Strothmann. DNA Computing and Molecular Programming – 21st International Conference (DNA21), Boston/Cambridge, MA, USA. August 19, 2015.Brief Announcement: On the Feasibility of Leader Election and Shape Formation with Self-Organizing Programmable Matter. Thim Strothmann. 2015 ACM Symposium on Principles of Distributed Computing (PODC ’15), Donostia-San Sebastian, Spain. July 21, 2015.
Poster Presentations
- Bio-Inspired Energy Distribution for Programmable Matter. Joshua J. Daymude and Jamison W. Weber. 26th International Conference on DNA Computing and Molecular Programming (DNA 2020), Virtual Event. September 17, 2020.
- Target Detection Using Algorithmic Matter. Rebecca Martin. Fulton Undergraduate Research Initiative Spring 2020 Symposium (FURI Spring 2020). Tempe, AZ, USA. April 24, 2020.
- Self-Organizing Particle Systems: an Abstraction of Programmable Matter. Joshua J. Daymude. Achievement Rewards for College Scientists (ARCS) Awards Dinner 2019, Phoenix, AZ, USA. April 26, 2019.
- Towards Hybrid Programmable Matter: Shape Recognition, Detection, and Sealing Algorithms for Finite Automaton Robots. Irina Kostitsyna. Highlights of Algorithms (HALG ’18), Amsterdam, Netherlands. June 4, 2018.
- Self-Organizing Particle Systems: an Abstraction of Programmable Matter. Joshua J. Daymude. Achievement Rewards for College Scientists (ARCS) Awards Dinner 2018, Phoenix, AZ, USA. April 20, 2018.
- Compaction and Expansion in Self-Organizing Particle Systems. Zahra Derakhshandeh. Biological Distributed Algorithms (BDA ’15), Boston, MA, USA. August 18-19, 2015.
- Compaction and Expansion in Self-Organizing Particle Systems. Joshua J. Daymude. 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO ’15), Montserrat, Spain. July 16, 2015.
Other Presentations
- Self-Organizing Particle Systems (SOPS). Andréa W. Richa. Tutorial at Dagstuhl Seminar 18331: Algorithmic Foundations of Programmable Matter, Schloss Dagstuhl, Germany. August 16, 2018.
- Convex Hull Formation for Programmable Matter. Joshua J. Daymude. Biological Distributed Algorithms (BDA ’17), Washington D.C., USA. July 28, 2017.
- Models and Algorithms for Programmable Matter. Dagstuhl Seminar 15402: Self-Assembly and Self-Organization in Computer Science and Biology, Schloss Dagstuhl, Germany. September 29, 2015.
- Programmable Matter: Models and Algorithms. Andréa W. Richa. Biological Distributed Algorithms (BDA ’14), Austin, TX, USA. October 12, 2014.
People
Current Team
Past Members and Collaborators
Alexandra Porter
Ph.D Student, Stanford University [website]
Ziad Abdelkarim
Project Manager, Dell Technologies [website]
Christopher Boor
Computer Science Undergraduate, Arizona State University[website]
Ryan Yiu
Software Engineer, American Express[website]
Noble Harasha
Computer Science Undergraduate, MIT[website]
Funding
- Collaborative Research: AF: Medium: Markov Chain Algorithms for Problems from Computer Science, Statistical Physics and Self-Organizing Particle Systems. Award #2106917. May. 2021 – Present.
- Foundations of Emergent Computation and Self-Organized Adaptation. DoD MURI (Multidisciplinary University Research Initiative) Award #W911NF-19-1-0233. Feb. 2019 – Present.
- Algorithms in the Field: Collaborative Research: A Distributed and Stochastic Algorithmic Framework for Active Matter. NSF CCF (Division of Computing and Communication Foundations): Algorithmic Foundations, Award #1637393. Sept. 2016 – Aug. 2018.
- Algorithms in the Field: Collaborative Research: Distributed and Stochastic Algorithms for Active Matter: Theory and Practice. NSF CCF (Division of Computing and Communication Foundations): Algorithmic Foundations Award #1733680. Jan. 2018 – Dec. 2020.
- Self-Organizing Particle Systems. NSF CCF (Division of Computing and Communication Foundations): Algorithmic Foundations Award #1422603. Aug. 2014 – July 2018 (estimated).
- Algorithmen für selbstorganisierende Partikelsysteme (Algorithms for Self-Organizing Particle Systems). DFG Project SCHE 1592/3-1. 2014 – 2017.
- EAGER: Self-Organizing Particle Systems: Models and Algorithms. NSF CCF (Division of Computing and Communication Foundations): Algorithmic Foundations Award #1353089. Sept. 2013 – Aug. 2015 (estimated).