Distributed leader election and computation of local identifiers for programmable matter

DOI10.1007/978-3-030-14094-6_11MaRDI QIDQ6051510zbMATH OpenOpenAlexFDO

Authors Nicolas Gastineau, Wahabou Abdou, Nader Mbarek, Olivier Togni

Publication date 20 October 2023

Published in Algorithms for Sensor Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.10461

zbMATH Keywords

graph coloringidentifierleader electionprogrammable matter

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The context of this paper is programmable matter, which consists of a set of computational elements, called particles, in an infinite graph. The considered infinite graphs are the square, triangular and king grids. Each particle occupies one vertex, can communicate with the adjacent particles, has the same clockwise direction and knows the local positions of neighborhood particles. Under these assumptions, we describe a new leader election algorithm affecting a variable to the particles, called the k-local identifier, in such a way that particles at close distance have each a different k-local identifier. For all the presented algorithms, the particles only need a O(1)-memory space.

Recommendations

• Improved Leader Election for Self-organizing Programmable Matter
• Leader election and shape formation with self-organizing programmable matter
• Deterministic Leader Election in Programmable Matter
• Leader election in plane cellular automata, only with left-right global convention
• CADbots: algorithmic aspects of manipulating programmable matter with finite automata

Cited in

(7)

• Leader election and shape formation with self-organizing programmable matter
• Improved Leader Election for Self-organizing Programmable Matter
• Deterministic Leader Election in Programmable Matter
• The canonical amoebot model: algorithms and concurrency control
• Efficient Deterministic Leader Election for Programmable Matter
• Stationary and deterministic leader election in self-organizing particle systems
• Deterministic self-stabilising leader election for programmable matter with constant memory

This page was built for publication: Distributed leader election and computation of local identifiers for programmable matter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6051510)