2026-07-26T19:54:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23072 2025-10-02T12:33:01Z ddc:004 open_access

Brief Announcement: Anonymous Distributed Localisation via Spatial Population Protocols Gąsieniec, Leszek Kuszner, Łukasz Latif, Ehsan Parasuraman, Ramviyas Spirakis, Paul Stachowiak, Grzegorz Population Protocols Distributed Localisation In the distributed localization problem (DLP), n anonymous robots (agents) A₀, …, A_{n-1} begin at arbitrary positions p₀, …, p_{n-1} ∈ S, where S is a Euclidean space. Initially, each agent A_i operates within its own coordinate system in S, which may be inconsistent with those of other agents. The primary goal in DLP is for agents to reach a consensus on a unified coordinate system that accurately reflects the relative positions of all points, p₀, …, p_{n-1}, in S. Extensive research on DLP has primarily focused on the feasibility and complexity of achieving consensus when agents have limited access to inter-agent distances, often due to missing or imprecise data. In this paper, however, we examine a minimalist, computationally efficient model of distributed computing in which agents have access to all pairwise distances, if needed. Specifically, we introduce a novel variant of population protocols, referred to as the spatial population protocols model. In this variant each agent can memorise one or a fixed number of coordinates, and when agents A_i and A_j interact, they can not only exchange their current knowledge but also either determine the distance d_{ij} between them in S (distance query model) or obtain the vector v→_{ij} spanning points p_i and p_j (vector query model). We present here a leader-based localisation protocol with distance queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leszek Gąsieniec and Łukasz Kuszner and Ehsan Latif and Ramviyas Parasuraman and Paul Spirakis and Grzegorz Stachowiak 2025 Is Part Of LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2025.19 urn:nbn:de:0030-drops-230726 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode