Safety Analysis of Parameterised Networks with Non-Blocking Rendez-Vous - Sorbonne Université Access content directly
Conference Papers Year : 2023

Safety Analysis of Parameterised Networks with Non-Blocking Rendez-Vous

Abstract

We consider networks of processes that all execute the same finite-state protocol and communicate via a rendez-vous mechanism. When a process requests a rendez-vous, another process can respond to it and they both change their control states accordingly. We focus here on a specific semantics, called non-blocking, where the process requesting a rendez-vous can change its state even if no process can respond to it. In this context, we study the parameterised coverability problem of a configuration, which consists in determining whether there is an initial number of processes and an execution allowing to reach a configuration bigger than a given one. We show that this problem is EXPSPACE-complete and can be solved in polynomial time if the protocol is partitioned into two sets of states, the states from which a process can request a rendez-vous and the ones from which it can answer one. We also prove that the problem of the existence of an execution bringing all the processes in a final state is undecidable in our context. These two problems can be solved in polynomial time with the classical rendez-vous semantics.
No file

Dates and versions

hal-04286027 , version 1 (14-11-2023)

Identifiers

Cite

Lucie Guillou, Arnaud Sangnier, Nathalie Sznajder. Safety Analysis of Parameterised Networks with Non-Blocking Rendez-Vous. 34th International Conference on Concurrency Theory, CONCUR 2023, Sep 2023, Antwerp, Belgium. pp.7:1-7:17, ⟨10.4230/LIPICS.CONCUR.2023.7⟩. ⟨hal-04286027⟩
16 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More