Analyzing guarded protocols: better cutoffs, more systems, more expressivity

DOI10.1007/978-3-319-73721-8_12MaRDI QIDQ3296331zbMATH OpenOpenAlexFDO

Authors Swen Jacobs, Mouhammad Sakr

Publication date 7 July 2020

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.01369

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We study cutoff results for parameterized verification and synthesis of guarded protocols, as introduced by Emerson and Kahlon (2000). Guarded protocols describe systems of processes whose transitions are enabled or disabled depending on the existence of other processes in certain local states. Cutoff results reduce reasoning about systems with an arbitrary number of processes to systems of a determined, fixed size. Our work is based on the observation that existing cutoff results for guarded protocols are often impractical, since they scale linearly in the number of local states of processes in the system. We provide new cutoffs that scale not with the number of local states, but with the number of guards in the system, which is in many cases much smaller. Furthermore, we consider natural extensions of the classes of systems and specifications under consideration, and present results for problems that have not been known to admit cutoffs before.

Recommendations

• Tight cutoffs for guarded protocols with fairness
• Parameterized verification of systems with global synchronization and guards
• Symmetry and Completeness in the Analysis of Parameterized Systems
• Parameterized model checking of rendezvous systems
• Parameterized model checking of networks of timed automata with Boolean guards

Cited in

(8)

• Structural Invariants for the Verification of Systems with Parameterized Architectures
• Parameterized synthesis of self-stabilizing protocols in symmetric networks
• Computing Parameterized Invariants of Parameterized Petri Nets
• Computing parameterized invariants of parameterized Petri nets
• Parameterized verification of systems with global synchronization and guards
• Tight cutoffs for guarded protocols with fairness
• Parameterized model checking of networks of timed automata with Boolean guards
• Checking deadlock-freedom of parametric component-based systems

This page was built for publication: Analyzing guarded protocols: better cutoffs, more systems, more expressivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3296331)