Anonymous Self-Stabilising Localisation via Spatial Population Protocols

Anonymous Self-Stabilising Localisation via Spatial Population Protocols | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Anonymous Self-Stabilising Localisation via Spatial Population Protocols Leszek Gąsieniec, Łukasz Kuszner, Ehsan Latif, Ramviyas Parasuraman, and 2 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-9368524/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 6 You are reading this latest preprint version Abstract In the distributed localisation problem (DLP), n anonymous robots (agents) A0, . . . ,An−1 are located at arbitrary points p0, . . . , pn−1 ∈ S, where S is a Euclidean space. Initially, each agent Ai 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 (jointly agreed) coordinate system, in which all agents receive unique labels (coordinates) that accurately reflect the relative distances between all points p0, . . . , pn−1 in S. Extensive research on DLP has primarily focus 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 contrast, this paper proposes a minimalist, computationally efficient distributed computing model where agents can query any pairwise relative positions, 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 Ai and Aj interact, they can not only exchange their current knowledge but also either determine the distance dij between them in S (distance query model) or obtain the vector −→vij spanning points pi and pj (vector query model). We propose and analyse several distributed localisation protocols, including: 1. Leader-based localisation protocol with distance queries We propose and analyse two leader-based localisation protocols that stabilise silently in o(n) time. These protocols leverage an efficient solution to the novel concept of multi-contact epidemic, a natural generalisation of the core communication tool in population protocols, known as the one-way epidemic. 2. Self-stabilising leader localisation protocol with distance queries We show how to effectively utilise a leader election mechanism within the leader-based localisation protocol to get a DLP protocol that self-stabilises silently in time O(n(log n/n)1/(k+1) log n) in k-dimensions. 3. Self-stabilising localisation protocol with vector queries We propose and analyse an optimally fast DLP protocol which self-stabilises silently in O(log n) time. Population Protocols Distributed Localisation Spatial Queries Self-Stabilisation Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviewers agreed at journal 16 Apr, 2026 Reviewers agreed at journal 13 Apr, 2026 Reviewers invited by journal 13 Apr, 2026 Editor assigned by journal 12 Apr, 2026 Submission checks completed at journal 10 Apr, 2026 First submitted to journal 09 Apr, 2026 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-9368524","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":624102967,"identity":"c283519e-de0b-4cb1-8b33-f820f09f5d84","order_by":0,"name":"Leszek Gąsieniec","email":"","orcid":"","institution":"University of Liverpool","correspondingAuthor":false,"prefix":"","firstName":"Leszek","middleName":"","lastName":"Gąsieniec","suffix":""},{"id":624102968,"identity":"ae05969f-ee3d-4a0a-aaef-2c9eec41b72a","order_by":1,"name":"Łukasz Kuszner","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA/ElEQVRIiWNgGAWjYBACPgY2MG0A5duASQkglsGlhQ1NSxpcCw+xWg4ToUUiLfHjjz8Mxgbnjz978HHP+cT5DswHb/Mw3MGn5bA0Dw+DmcGNhHTDGc9uJ248wJZszcPwDI+W9AZpoENsDG4wHJPmOQDU0sBjJs3DcBifluafPwyAWs4fbJP+c+AcUAv/NwJa0o5J8CQAHXYgmU2a4cCBxPkMPGz4tfA8S7PmOSBhLHkjjU2y50Cy8QZmNmPLOQa4/cLPnmZ888cfG8M+YIhJ/DhgJzu/vfnhjTcVd+RwaYECCQTTABw1BgcI6EAG8g1gihQto2AUjIJRMMwBABq6T8Et/Bo5AAAAAElFTkSuQmCC","orcid":"","institution":"University of Gdańsk","correspondingAuthor":true,"prefix":"","firstName":"Łukasz","middleName":"","lastName":"Kuszner","suffix":""},{"id":624102969,"identity":"0c548735-55b5-458b-9989-72cf5b5a25e9","order_by":2,"name":"Ehsan Latif","email":"","orcid":"","institution":"University of Georgia","correspondingAuthor":false,"prefix":"","firstName":"Ehsan","middleName":"","lastName":"Latif","suffix":""},{"id":624102970,"identity":"0ffc4bd9-5aa1-47a8-a885-5ae83d639d88","order_by":3,"name":"Ramviyas Parasuraman","email":"","orcid":"","institution":"University of Georgia","correspondingAuthor":false,"prefix":"","firstName":"Ramviyas","middleName":"","lastName":"Parasuraman","suffix":""},{"id":624102971,"identity":"2d28db30-92b5-48e2-8882-16f0b63b0ed9","order_by":4,"name":"Paul Spirakis","email":"","orcid":"","institution":"University of Liverpool","correspondingAuthor":false,"prefix":"","firstName":"Paul","middleName":"","lastName":"Spirakis","suffix":""},{"id":624102972,"identity":"e984d02e-a28d-4e60-b205-9a0ad44aa110","order_by":5,"name":"Grzegorz Stachowiak","email":"","orcid":"","institution":"University of Wrocław","correspondingAuthor":false,"prefix":"","firstName":"Grzegorz","middleName":"","lastName":"Stachowiak","suffix":""}],"badges":[],"createdAt":"2026-04-09 12:23:55","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-9368524/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-9368524/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":107430172,"identity":"803cef85-dbb6-4f0d-84de-101471c677ad","added_by":"auto","created_at":"2026-04-21 12:12:29","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":268959,"visible":true,"origin":"","legend":"","description":"","filename":"snarticle.pdf","url":"https://assets-eu.researchsquare.com/files/rs-9368524/v1_covered_cc8ccd07-5d88-4f0f-9654-3473db862213.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Anonymous Self-Stabilising Localisation via Spatial Population Protocols","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"distributed-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"dist","sideBox":"Learn more about [Distributed Computing](http://link.springer.com/journal/446)","snPcode":"446","submissionUrl":"https://submission.nature.com/new-submission/446/3","title":"Distributed Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Population Protocols, Distributed Localisation, Spatial Queries, Self-Stabilisation","lastPublishedDoi":"10.21203/rs.3.rs-9368524/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-9368524/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eIn the distributed localisation problem (DLP), n anonymous robots (agents) A0, . . . ,An−1 are located at arbitrary points p0, . . . , pn−1 ∈ S, where S is a Euclidean space. Initially, each agent Ai 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 (jointly agreed) coordinate system, in which all agents receive unique labels (coordinates) that accurately reflect the relative distances between all points p0, . . . , pn−1 in S. Extensive research on DLP has primarily focus 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 contrast, this paper proposes a minimalist, computationally efficient distributed computing model where agents can query any pairwise relative positions, 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 Ai and Aj interact, they can not only exchange their current knowledge but also either determine the distance dij between them in S (distance query model) or obtain the vector −→vij spanning points pi and pj (vector query model). We propose and analyse several distributed localisation protocols, including: 1. Leader-based localisation protocol with distance queries We propose and analyse two leader-based localisation protocols that stabilise silently in o(n) time. These protocols leverage an efficient solution to the novel concept of multi-contact epidemic, a natural generalisation of the core communication tool in population protocols, known as the one-way epidemic. 2. Self-stabilising leader localisation protocol with distance queries We show how to effectively utilise a leader election mechanism within the leader-based localisation protocol to get a DLP protocol that self-stabilises silently in time O(n(log n/n)1/(k+1) log n) in k-dimensions. 3. Self-stabilising localisation protocol with vector queries We propose and analyse an optimally fast DLP protocol which self-stabilises silently in O(log n) time.\u003c/p\u003e","manuscriptTitle":"Anonymous Self-Stabilising Localisation via Spatial Population Protocols","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-04-21 12:10:47","doi":"10.21203/rs.3.rs-9368524/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"reviewerAgreed","content":"6409225894841707048438366243905848455","date":"2026-04-16T07:08:56+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"203592635872892222268531290387303673403","date":"2026-04-13T20:04:42+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-04-13T15:57:16+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-04-12T06:02:54+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-04-10T08:45:48+00:00","index":"","fulltext":""},{"type":"submitted","content":"Distributed Computing","date":"2026-04-09T12:19:33+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"distributed-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"dist","sideBox":"Learn more about [Distributed Computing](http://link.springer.com/journal/446)","snPcode":"446","submissionUrl":"https://submission.nature.com/new-submission/446/3","title":"Distributed Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"50992694-4588-471c-acfc-a6b86c21bd38","owner":[],"postedDate":"April 21st, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-04-21T12:10:47+00:00","versionOfRecord":[],"versionCreatedAt":"2026-04-21 12:10:47","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-9368524","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-9368524","identity":"rs-9368524","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}