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

FoSSaCSb

N. Bertrand, P. Fournier, A. Sangnier. Playing with probabilities in reconfigurable broadcast networks. In 17th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS'14, Springer (ed.), LNCS, Volume 8412, Pages 134-148, Grenoble, France, April 2014.

Download [help]

Download paper: Doi page

Download Hal paper: Hal : Hyper Archive en ligne

Abstract

We study verification problems for a model of network with the following characteristics: the number of entities is parametric, communication is performed through broadcast with adjacent neighbors, entities can change their internal state probabilistically and reconfiguration of the communication topology can happen at any time. The semantics of such a model is given in term of an infinite state system with both non deterministic and probabilistic choices. We are interested in qualitative problems like whether there exists an initial topology and a resolution of the non determinism such that a configuration exhibiting an error state is almost surely reached. We show that all the qualitative reachability problems are decidable and some proofs are based on solving a 2 player game played on the graphs of a reconfigurable network with broadcast with parity and safety objectives

Contact

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

BibTex Reference

@InProceedings{FoSSaCSb,
   Author = {Bertrand, N. and Fournier, P. and Sangnier, A.},
   Title = {Playing with probabilities in reconfigurable broadcast networks},
   BookTitle = {17th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS'14},
   editor = {Springer, },
   Volume = {8412},
   Pages = {134--148},
   Series = {LNCS},
   Address = {Grenoble, France},
   Month = {April},
   Year = {2014}
}

EndNote Reference [help]

Get EndNote Reference (.ref)