Universal pattern formation by oblivious robots under sequential schedulers
Distributed Computing · 2026-06 · 39 (2)
DOI: 10.1007/s00446-026-00504-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Distributed Computing, online erschienen am 25.03.2026. Verfasst von Paola Flocchini und 4 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, Italian National 921 Group for Scientific Computation INdAM.
Abstract (Originalsprache)
We study the computational power that oblivious robots operating in the plane have under sequential schedulers. We show that this power is much stronger than the obvious capacity these schedulers offer of breaking symmetry, and thus to create a leader. In fact, we prove that under any sequential scheduler, robots are capable of solving problems that are unsolvable even with a leader under the fully synchronous scheduler FSYNC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {FSYNC}$$\end{document}. More precisely, we consider the class of pattern formation problems, and focus on the most general problem in this class, Universal Pattern Formation (UPF), which requires the robots to form every pattern given in input, starting from any initial configuration (where some robots may occupy the same point, hence forming a multiplicity). We first show that UPF is unsolvable under FSYNC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {FSYNC}$$\end{document}, even if the robots are endowed with additional strong capabilities (multiplicity detection, rigid movement, agreement on coordinate systems, presence of a unique leader). On the other hand, we prove that, except for point formation (Gathering), UPF is solvable under any sequential scheduler without any additional assumptions. We then turn our attention to the Gathering problem, and prove that weak multiplicity detection (the ability to detect a multiplicity but not the exact number of robots forming it) is necessary and sufficient for solvability under sequential schedulers. The results obtained show that the computational power of the robots under FSYNC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {FSYNC}$$\end{document} (where Gathering is solvable without any multiplicity detection) and that under sequential schedulers are orthogonal.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- Italian National 921 Group for Scientific Computation INdAM
Zitieren
APA
Flocchini, P., Navarra, A., Pattanayak, D., Piselli, F., & Santoro, N. (2026). Universal pattern formation by oblivious robots under sequential schedulers. Distributed Computing, 39(2). https://doi.org/10.1007/s00446-026-00504-3
Vancouver
Flocchini P, Navarra A, Pattanayak D, Piselli F, Santoro N. Universal pattern formation by oblivious robots under sequential schedulers. Distributed Computing. 2026;39(2). doi:10.1007/s00446-026-00504-3
BibTeX
@article{Flocchini2026,
author = {Flocchini, Paola and Navarra, Alfredo and Pattanayak, Debasish and Piselli, Francesco and Santoro, Nicola},
title = {Universal pattern formation by oblivious robots under sequential schedulers},
journal = {Distributed Computing},
year = {2026},
volume = {39},
number = {2},
doi = {10.1007/s00446-026-00504-3}
}
EUVIMED