1 Search Results for "Ryabinin, Fedor"

Reachability in Distributed Memory Automata

Authors: Benedikt Bollig, Fedor Ryabinin, and Arnaud Sangnier

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

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.

Cite as

Benedikt Bollig, Fedor Ryabinin, and Arnaud Sangnier. Reachability in Distributed Memory Automata. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

  author =	{Bollig, Benedikt and Ryabinin, Fedor and Sangnier, Arnaud},
  title =	{{Reachability in Distributed Memory Automata}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.13},
  URN =		{urn:nbn:de:0030-drops-134472},
  doi =		{10.4230/LIPIcs.CSL.2021.13},
  annote =	{Keywords: Distributed algorithms, Atomic snapshot objects, Register automata, Reachability}
  • Refine by Author
  • 1 Bollig, Benedikt
  • 1 Ryabinin, Fedor
  • 1 Sangnier, Arnaud

  • Refine by Classification
  • 1 Theory of computation → Concurrency

  • Refine by Keyword
  • 1 Atomic snapshot objects
  • 1 Distributed algorithms
  • 1 Reachability
  • 1 Register automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail