License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2015.44
URN: urn:nbn:de:0030-drops-53796
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5379/
Go to the corresponding LIPIcs Volume Portal

Bertrand, Nathalie ; Fournier, Paulin ; Sangnier, Arnaud

Distributed Local Strategies in Broadcast Networks

pdf-format:
19.pdf (0.5 MB)

Abstract

We study the problems of reaching a specific control state, or converging to a set of target states, in networks with a parameterized number of identical processes communicating via broadcast. To reflect the distributed aspect of such networks, we restrict our attention to executions in which all the processes must follow the same local strategy that, given their past performed actions and received messages, provides the next action to be performed. We show that the reachability and target problems under such local strategies are NP-complete, assuming that the set of receivers is chosen non-deterministically at each step. On the other hand, these problems become undecidable when the communication topology is a clique. However, decidability can be regained for reachability under the additional assumption that all processes are bound to receive the broadcast messages.

BibTeX - Entry

@InProceedings{bertrand_et_al:LIPIcs:2015:5379,
  author =	{Nathalie Bertrand and Paulin Fournier and Arnaud Sangnier},
  title =	{{Distributed Local Strategies in Broadcast Networks}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{44--57},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Luca Aceto and David de Frutos Escrig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5379},
  URN =		{urn:nbn:de:0030-drops-53796},
  doi =		{10.4230/LIPIcs.CONCUR.2015.44},
  annote =	{Keywords: Broadcast networks, parameterized verification, local strategies}
}

Keywords: Broadcast networks, parameterized verification, local strategies
Collection: 26th International Conference on Concurrency Theory (CONCUR 2015)
Issue Date: 2015
Date of publication: 26.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI