Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter
Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter
复制标题
三维可编程事物中的异步确定性领导者选举
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
A. Richa
中科院分区：
文献类型：
--
作者：
Joseph L. Briones;Tishya Chhabra;Joshua J. Daymude;A. Richa
三十年来，为了实现可编程物质（一种可以根据用户输入或对其环境的响应而改变其物理属性的物质）的科学努力，模块化机器人系统的工程和相应的集体行为算法理论都取得了许多进展。然而，虽然模块化机器人的设计通常会解决现实三维 (3D) 空间的挑战，但算法理论仍然主要关注平面和平面图等 2D 抽象。在这项工作中，我们使用面心立方 (FCC) 晶格来表示空间并定义局部空间方向，将可编程物质的规范 amoebot 模型的 3D 几何空间变体形式化。然后，我们给出了一种在连接的、可收缩的 2D 或 3D 几何 amoebot 系统中进行领导者选举的分布式算法，该算法在不公平的连续对手下，在 $\mathcal{O}(n)$ 轮中确定性地选举出一位领导者，其中 $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 $\mathcal{O}(n)$ 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.
自组织可编程物质的领导者选举和形态形成
DOI：
10.1007/978-3-319-21999-8_8
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Zahra Derakhshandeh;Robert Gmyr;Thim Strothmann;Rida A. Bazzi;Andrea W. Richa;Christian Scheideler
通讯作者：
Christian Scheideler