Asynchronous Silent Programmable Matter Achieves Leader Election and Compaction

作     者：D'Angelo, Gianlorenzo D'Emidio, Mattia Das, Shantanu Navarra, Alfredo Prencipe, Giuseppe 

作者机构：Gran Sasso Sci Inst I-67100 Laquila Italy Univ Aquila Dept Informat Engn Comp Sci & Math I-67100 Laquila Italy Aix Marseille Univ LIS CNRS Univ Toulon F-13288 Marseille France Univ Perugia Dept Math & Comp Sci I-06123 Perugia Italy Univ Pisa Dept Comp Sci I-56126 Pisa Italy 

出 版 物：《IEEE ACCESS》 (IEEE Access)

年 卷 期：2020年第8卷

页      面：207619-207634页

核心收录：

基　　金：Ministero dell'Istruzione, Universita e Ricerca (MIUR) PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets" Gruppo Nazionale per il Calcolo Scientifico dell'Istituto Nazionale di Alta Matematica (GNCS-INdAM) Universita di Pisa, Italy [PRA_2018_43] Project "ASSIOMI-Algorithms, Systems and Devices for Machine Monitoring and Diagnosing in Smart Factories (Algoritmi Sistemi e diSpositivI per mOnitoraggio e diagnostica di Macchine per le fabbriche Intelligenti) 

主　　题：Voting Computational modeling Compaction Task analysis Solid modeling Lattices Delays Programmable matter swarm robotics self-organizing systems leader election compaction finite automata distributed algorithms 

摘      要：We study models and algorithms for Programmable Matter (PM), that is matter with the ability to change its physical properties (e.g., shape or optical properties) in a programmable fashion. PM can be implemented by assembling a system of weak self-organizing computational elements, called particles, that can be programmed via distributed algorithms to collectively achieve some global task. Recent advances in the production of nanotechnologies have rendered such systems increasingly possible in practice, thus triggering research interests from many areas of computer science. The most established models for PM assume that particles: are modeled as finite state automata;are all identical, executing the same algorithm based on local observation of the surroundings;live and operate in the cells of a hexagonal grid;can move from one cell to another by repeatedly alternating between a contracted state (a particle occupies one cell) and an expanded state (a particle occupies two neighboring cells). Given these elementary features, it is rather hard to design distributed algorithms even for basic tasks and, in fact, all existing solutions to solve fundamental problems via PM have resorted to endowing PM systems with various capabilities to overcome such hardness, thus assuming quite unrealistic features. In this paper, we move toward more realistic computational models for PM. Specifically, we first introduce SILBOT, a new modeling approach that relaxes several assumptions used in previous ones. Second, we present a distributed algorithm to solve, in the SILBOT model, a foundational primitive for PM, namely Leader Election. This algorithm works in O(n) rounds for all initial configurations of n particles that are both connected (i.e. particles induce a connected graph) and compact (i.e. without holes, that is no empty cells surrounded by particles occur). As usual in asynchronous contexts, a round is intended as the time within which all particles have been activated at leas