Algorithmic Foundations of Circuit-Based Programmable Matter

点击翻译按钮获取中文摘要

In 2014, we proposed the amoebot model for the rigorous algorithmic study of programmable matter. Since then, the model has gained considerable momentum, but it only allows slow shape transformations. Recently, we proposed a reconfigurable circuit extension of the amoebot model in order to quickly disseminate information in an amoebot structure and showed that various fundamental computational tasks like leader election or compass alignment can be solved significantly faster than in the original model. Based on this extension, we intend to develop highly scalable distributed algorithms for shape transformations, the detection of errors in shapes, and for a best possible matching of a given shape with some target shape. Such highly scalable algorithms are vital in order to make our research results sufficiently attractive for a technical realization.