Invited Paper: Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter
Invited Paper: Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter
复制标题
特邀论文：三维可编程物质中的异步确定性领导者选举
DOI：
10.1145/3571306.3571389
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Richa, Andréa W.
中科院分区：
文献类型：
--
作者：
Briones, Joseph L.;Chhabra, Tishya;Daymude, Joshua J.;Richa, Andréa W.
三十年来，为了实现可编程物质（一种可以根据用户输入或对其环境的响应而改变其物理属性的物质）的科学努力，模块化机器人系统的工程和相应的集体行为算法理论都取得了许多进展。然而，虽然模块化机器人的设计通常会解决现实三维 (3D) 空间的挑战，但算法理论仍然主要关注平面和平面图等 2D 抽象。在这项工作中，我们使用面心立方 (FCC) 晶格来表示空间并定义局部空间方向，将可编程物质的规范 amoebot 模型的 3D 几何空间变体形式化。然后，我们给出了一种在连接的、可收缩的 2D 或 3D 几何 amoebot 系统中进行领导者选举的分布式算法，该算法在不公平的顺序对手下确定性地在一轮中选出一位领导者，其中 n 是系统中 amoebot 的数量。然后，我们演示如何使用 amoebot 算法的并发控制框架 (DISC 2021) 对该算法进行转换，以获得第一个已知的 amoebot 算法（在 2D 和 3D 空间中），以解决不公平异步对手下的领导者选举问题。
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 formalize the 3D geometric space variant for the canonical 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 leader election in connected, contractible 2D or 3D geometric amoebot systems that deterministically elects exactly one leader in rounds under an unfair sequential adversary, where n is the number of amoebots in the system. We then demonstrate 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.