Distributed local strategies in broadcast networks

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.
Type de document :
Rapport
[Research Report] Inria Rennes. 2015
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01170796
Contributeur : Nathalie Bertrand <>
Soumis le : jeudi 2 juillet 2015 - 12:30:56
Dernière modification le : mardi 16 janvier 2018 - 15:54:22
Document(s) archivé(s) le : mardi 25 avril 2017 - 22:28:05

Fichier

concur-techrep.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01170796, version 1

Citation

Nathalie Bertrand, Paulin Fournier, Arnaud Sangnier. Distributed local strategies in broadcast networks. [Research Report] Inria Rennes. 2015. 〈hal-01170796〉

Partager

Métriques

Consultations de la notice

293

Téléchargements de fichiers

117