Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

bertrand:hal-01170796

N. Bertrand, P. Fournier, A. Sangnier. Distributed local strategies in broadcast networks. Research Report Inria Rennes, July 2015.

Download [help]

Download Hal paper: Hal : Hyper Archive en ligne

Download paper: (link)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

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, decid-ability can be regained for reachability under the additional assumption that all processes are bound to receive the broadcast messages

Contact

Nathalie Bertrand http://www.irisa.fr/prive/nbertran/

BibTex Reference

@TechReport{bertrand:hal-01170796,
   Author = {Bertrand, N. and Fournier, P. and Sangnier, A.},
   Title = {Distributed local strategies in broadcast networks},
   Institution = {Inria Rennes},
   Month = {July},
   Year = {2015}
}

EndNote Reference [help]

Get EndNote Reference (.ref)