Energy-Constrained Programmable Matter Under Unfair Adversaries
This work provides a foundational tool for algorithm designers in programmable matter, enabling them to develop energy-agnostic algorithms that automatically gain energy-constrained correctness under unfair adversaries.
The authors present a general energy distribution framework for the amoebot model of programmable matter that converts energy-agnostic algorithms into energy-constrained ones with equivalent behavior and O(n^2) runtime overhead under an unfair adversary. They demonstrate compatibility with existing leader election and shape formation algorithms, and show the framework can be composed with concurrency control.
Individual modules of programmable matter participate in their system's collective behavior by expending energy to perform actions. However, not all modules may have access to the external energy source powering the system, necessitating a local and distributed strategy for supplying energy to modules. In this work, we present a general energy distribution framework for the canonical amoebot model of programmable matter that transforms energy-agnostic algorithms into energy-constrained ones with equivalent behavior and an $\mathcal{O}(n^2)$-round runtime overhead -- even under an unfair adversary -- provided the original algorithms satisfy certain conventions. We then prove that existing amoebot algorithms for leader election (ICDCN 2023) and shape formation (Distributed Computing, 2023) are compatible with this framework and show simulations of their energy-constrained counterparts, demonstrating how other unfair algorithms can be generalized to the energy-constrained setting with relatively little effort. Finally, we show that our energy distribution framework can be composed with the concurrency control framework for amoebot algorithms (Distributed Computing, 2023), allowing algorithm designers to focus on the simpler energy-agnostic, sequential setting but gain the general applicability of energy-constrained, asynchronous correctness.