Complexity of Coverability in Bounded Path Broadcast Networks

Broadcast networks are a formalism of distributed computation that allows one to model networks of identical nodes communicating through message broadcasts over a communication topology that does not change over the course of executions. The coverability problem for such networks consists of deciding if there is a run of the network from some initial configuration in which some node reaches a given state. This problem is known to be undecidable (Delzanno, Sangnier, and Zavattaro, CONCUR 2010). In the same paper, the authors prove that, if the underlying communication topology has a bound on the longest path, then the coverability problem becomes decidable. We provide complexity results for the above problem and prove that the coverability problem for bounded path topologies is $\mathbf{F}_{\epsilon_0}$-complete, where $\mathbf{F}_{\epsilon_0}$ is a class in the fast-growing hierarchy of complexity classes. This solves an open problem of Hasse, Schmitz and Schnoebelen (LMCS, Vol 10, Issue 4). This work has been published at FSTTCS 2021.

Authors

• A. R. Balasubramanian Technical University of Munich

Keywords

No keywords are indexed for this paper.