Parameterized model checking of networks of timed automata with Boolean guards

Autor: Francesco Spegni, Luca Spalazzi
Rok vydání: 2020
Předmět:
Zdroj: Theoretical Computer Science. 813:248-269
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2019.12.026
Popis: Parameterized model checking is a formal verification technique for verifying that some specifications hold in systems consisting of many similar cooperating but indistinguishable processes. The problem is known to be undecidable in general, even when restricted to reachability properties. To overcome this limitation, several techniques have been explored to address specific system families, logical formulas or topologies of process networks. Some use the notion of cutoff, i.e. if a certain property is verified for systems up to a certain size (the cutoff) then it is verified for systems of any size. Here we analyze the case of networks consisting of an arbitrary number of timed automata that can synchronize by looking at which state the neighbors are currently. We show that cutoffs exist independently from the checked formula, with or without a distinguished process acting as controller. We show how, exploiting the cutoffs, we can obtain upper bounds on complexity of the parameterized model-checking problem. Finally, we show how to use the theoretical results in order to model and verify a distributed algorithm for clock synchronization based on gossip techniques.
Databáze: OpenAIRE
Externí odkaz: