Parameterized Analysis of Reconfigurable Broadcast Networks
Open Access
- 29 March 2022
- book chapter
- Published by Springer Nature
- p. 61-80
Abstract
Reconfigurable broadcast networks (RBN) are a model of distributed computation in which agents can broadcast messages to other agents using some underlying communication topology which can change arbitrarily over the course of executions. In this paper, we conduct parameterized analysis of RBN. We consider cubes, (infinite) sets of configurations in the form of lower and upper bounds on the number of agents in each state, and we show that we can evaluate boolean combinations over cubes and reachability sets of cubes in . In particular, reachability from a cube to another cube is a -complete problem.To prove the upper bound for this parameterized analysis, we prove some structural properties about the reachability sets and the symbolic graph abstraction of RBN, which might be of independent interest. We justify this claim by providing two applications of these results. First, we show that the almost-sure coverability problem is -complete for RBN, thereby closing a complexity gap from a previous paper [3]. Second, we define a computation model using RBN, à la population protocols, called RBN protocols. We characterize precisely the set of predicates that can be computed by such protocols.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The complexity of verifying population protocolsDistributed Computing, 2021
- Liveness in Broadcast NetworksLecture Notes in Computer Science, 2019
- Parameterized Analysis of Immediate Observation Petri Nets2019
- Playing with Probabilities in Reconfigurable Broadcast Networks2014
- Parameterized Verification of Ad Hoc Networks2010
- The computational power of population protocolsDistributed Computing, 2007
- Computation in networks of passively mobile finite-state sensorsDistributed Computing, 2006
- Reachability in Networks of Register Protocols under Stochastic Schedulers
- Parameterized Verification of Many Identical Probabilistic Timed Processes
- On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks