2026-08-11T08:34:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13447 2024-03-06T10:52:06Z ddc:004 open_access

Reachability in Distributed Memory Automata Bollig, Benedikt Ryabinin, Fedor Sangnier, Arnaud Distributed algorithms Atomic snapshot objects Register automata Reachability We introduce Distributed Memory Automata, a model of register automata suitable to capture some features of distributed algorithms designed for shared-memory systems. In this model, each participant owns a local register and a shared register and has the ability to change its local value, to write it in the global memory and to test atomically the number of occurrences of its value in the shared memory, up to some threshold. We show that the control-state reachability problem for Distributed Memory Automata is Pspace-complete for a fixed number of participants and is in Pspace when the number of participants is not fixed a priori. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benedikt Bollig and Fedor Ryabinin and Arnaud Sangnier 2021 Is Part Of LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2021.13 urn:nbn:de:0030-drops-134472 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.13 eng https://creativecommons.org/licenses/by/3.0/legalcode