Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter

Abstract

Over three decades of scientific endeavors to realize programmable matter, a substance that can change its physical properties based on user input or responses to its environment, there have been many advances in both the engineering of modular robotic systems and the corresponding algorithmic theory of collective behavior. However, while the design of modular robots routinely addresses the challenges of realistic three-dimensional (3D) space, algorithmic theory remains largely focused on 2D abstractions such as planes and planar graphs. In this work, we present the 3D geometric space variant for the well-established amoebot model of programmable matter, using the face-centered cubic (FCC) lattice to represent space and define local spatial orientations. We then give a distributed algorithm for the classical problem of leader election that can be applied to 2D or 3D geometric amoebot systems, proving that it deterministically elects exactly one leader in $\mathcal{O}(n)$ rounds under an unfair sequential adversary, where $n$ is the number of amoebots in the system. We conclude by demonstrating how this algorithm can be transformed using the concurrency control framework for amoebot algorithms (DISC 2021) to obtain the first known amoebot algorithm, both in 2D and 3D space, to solve leader election under an unfair asynchronous adversary.

Publication
Submitted to LATIN 2022
Joseph L. Briones
Joseph L. Briones
PhD Student, Computer Science
Tishya Chhabra
Tishya Chhabra
High School Research Assistant
Joshua J. Daymude
Joshua J. Daymude
Assistant Professor, Computer Science

I am a Christian and assistant professor in computer science studying collective emergent behavior and programmable matter through the lens of distributed computing, stochastic processes, and bio-inspired algorithms. I also love gaming and playing music.

Andréa W. Richa
Andréa W. Richa
Professor of Computer Science

Related