Affordable Access

Access to the full text

Reachability in Distributed Memory Automata

Authors
  • Bollig, Benedikt
  • Ryabinin, Fedor
  • Sangnier, Arnaud
Publication Date
Jan 01, 2021
Identifiers
DOI: 10.4230/LIPIcs.CSL.2021.13
OAI: oai:drops-oai.dagstuhl.de:13447
Source
Dagstuhl Research Online Publication Server
Keywords
Language
English
License
Green
External links

Abstract

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.

Report this publication

Statistics

Seen <100 times