Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.106
URN: urn:nbn:de:0030-drops-62416
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6241/
Bouyer, Patricia ; Markey, Nicolas ; Randour, Mickael ; Sangnier, Arnaud ; Stan, Daniel
Reachability in Networks of Register Protocols under Stochastic Schedulers
| pdf-format: |
|
Abstract
We study the almost-sure reachability problem in a distributed system obtained as the asynchronous composition of N copies (called processes) of the same automaton (called protocol), that can communicate via a shared register with finite domain. The automaton has two types of transitions: write-transitions update the value of the register, while read-transitions move to a new state depending on the content of the register. Non-determinism is resolved by a stochastic scheduler. Given a protocol, we focus on almost-sure reachability of a target state by one of the processes. The answer to this problem naturally depends on the number N of processes. However, we prove that our setting has a cut-off property: the answer to the almost-sure reachability problem is constant when N is large enough; we then develop an EXPSPACE algorithm deciding whether this constant answer is positive or negative.
BibTeX - Entry
@InProceedings{bouyer_et_al:LIPIcs:2016:6241,
author = {Patricia Bouyer and Nicolas Markey and Mickael Randour and Arnaud Sangnier and Daniel Stan},
title = {{Reachability in Networks of Register Protocols under Stochastic Schedulers}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {106:1--106:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6241},
URN = {urn:nbn:de:0030-drops-62416},
doi = {10.4230/LIPIcs.ICALP.2016.106},
annote = {Keywords: Networks of Processes, Parametrized Systems, Stochastic Scheduler, Almost-sure Reachability, Cut-Off Property}
}
| Keywords: | Networks of Processes, Parametrized Systems, Stochastic Scheduler, Almost-sure Reachability, Cut-Off Property | |
| Seminar: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 23.08.2016 |
