¹¹institutetext: RMIT University, Melbourne, Australia ¹¹email: {heinz.schmidt, james.harland, ian.peake, maria.spichkova}@rmit.edu.au ²²institutetext: Norwegian University of Science and Technology (NTNU), Trondheim, Norway
²²email: {peter.herrmann,ergys.puka}@ntnu.no

Spatio-Temporal Analysis of Concurrent Networks

Heinz Schmidt 11 0000-0001-6278-4793 Peter Herrmann 22 0000-0003-3830-466X Maria Spichkova 11 0000-0001-6882-1444 James Harland 11 0000-0001-8640-5137 Ian Peake 11 0000-0003-2136-5714 Ergys Puka 22 0000-0002-4257-3232

Abstract

Many very large-scale systems are networks of cyber-physical systems in which humans and autonomous software agents cooperate. To make the cooperation safe for the humans involved, the systems have to follow protocols with rigid real-time and real-space properties, but they also need to be capable of making competitive and collaborative decisions with varying rewards and penalties. Due to these tough requirements, the construction of system control software is often very difficult. This calls for applying a model-based engineering approach, which allows one to formally express the time and space properties and use them as guidance for the whole engineering process from requirement definition via system design to software development. Moreover, it is beneficial, if one can verify with acceptable effort, that the time and space requirements are preserved throughout the development steps. This paper focuses on modelling spatio-temporal properties and their model-checking and simulation using different analysis tools in combination with the methods and tool extensions proposed here. To this end, we provide an informal overview of CASTeL, our Concurrent Alliances Spatio-Temporal Logic. CASTeL is stochastic and includes real-time concurrency and real-space distribution.

Preprint. Accepted to the 21th International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (MobiQuitous 2024). Final version to be published by Springer (In Press).

1 Introduction

Very Large Scale Collaborative (VLSC) systems comprise defence, logistics, healthcare, and transport systems (including networked and autonomous vehicles) as well as widely distributed cloud computing and social networks, which may include millions of customers. Many of these VLSC systems are cyber-physical systems (CPS) [8], others are cyber-social systems (CSS), and some are both [1]. A CPS operates, monitors and controls physical infrastructure such as power and transport networks or manufacturing sites. A CSS involves humans with mobile devices and many configurations and preferences. Cooperative intelligent transport systems are examples of uniting CPS and CSS, which include vehicle-to-vehicle and vehicle-to-infrastructure communication and wearable mobile devices that combine automated agents with human decision-making. An increasing portion of VLSC software is generated using rapid development tools and, more recently, generative Artificial Intelligence. Such systems often exhibit a significant number of program errors, which require automatic detection, reporting, correction and other responses in the large, that have been well studied in the literature, see, e.g., [5].

Our approach is based on abstract concurrent behaviour modelling with Petri Nets (PNs) and their use for model-checking stochastic logic specifications in Computation Tree Logic (CTL) variants [14]. These logics include notions of abstract players (agents), with and without reward/penalty and other utility cost structures. They have a long history of model-checking over diverse PN model classes. PNs are a versatile form of state-transition systems that are suited to model system behaviour on very different levels of abstraction. For instance, one can use them to specify limited synchronisation capabilities provided by integer semaphores, train rail segments, or car traffic crossings with limited capacity.

The relationship between different classes of PNs and various temporal logics is well known, which means that PNs can be considered as abstract, logical, operational, and executable specifications. In particular, via model-checking one can formally carry out various analyses such as verifying structural properties of the nets, proving purely logical inference on the level of specified formulae, or simulating dynamic behaviour by executing the net either exhaustively or stochastically, in search of counter-examples that violate a logical formula.

This paper builds on our prior work for model-based and architecture-aware analysis of cyber-physical systems using a combination of dependent finite state machine interface descriptions, based on state-machine decomposable Petri Nets [32]. Further, this work is based on core aspects of readability that we introduced in [31].

Contributions: This paper proposes a model-driven approach called CASTeL, which is short for Concurrent Alliances Spatio-Temporal Logic. CASTeL makes the modelling of decisions, tactics and strategies in competitive and cooperative systems possible. Moreover, we show how one can use model-checking to verify, whether CASTeL-formulae are realized by Coloured Stochastic Petri Nets (CSPNs). Besides the traditional strengths of modularity and temporal concurrency of CSPNs, the approach includes spatial reasoning about the enforceability of properties.

Outline: The rest of the paper is organised as follows. Section 2 introduces a motivating scenario for the proposed approach, while Sect. 3 informally highlights features of our CASTeL specifications and PN models. Section 4 provides an overview of related approaches. Finally, Sect. 5 summarises the paper and suggests future work.

2 Motivating scenario

In this section, we introduce our motivating scenario, which is about context-aware communication protocols for cellular dead spot mitigation. Vehicles cooperating with each other and their infrastructure to realize Intelligent Transportation Systems (ITS), often suffer from the presence of dead spots, i.e., areas with no mobile network coverage. Dead spots are quite common on large land masses such as Australia and Canada, where very few people live outside larger population centres. One example in Australia is a 300+km portion of the Silver Highway in New South Wales (NSW) between Mildura and Broken Hill.

To alleviate this problem, we created special communication protocols which use opportunistic mobile ad hoc networks between nearby vehicles in a dead spot to alleviate transmission delays, see [26, 27, 29]. If the vehicles have reasonable estimates of their dead spot exit times, the ad hoc networks make the transfer of messages to those vehicles possible, that are anticipated to regain connectivity fastest. The protocols were simulated using the versatile traffic simulator SUMO [24]. The simulations have shown that using the context-aware protocols and the ad hoc networks may reduce the average waiting times in a dead spot by more than 40% [28]. While various vehicular network technologies can be used to realise ad hoc networks between vehicles, we prefer the popular WiFi Direct protocol [35], available on most state-of-the-art mobile phones. It allows us to communicate over a distance of up to 200 meters, which is sufficient in most cases, see [28]. In this paper, we assume that the WiFi Direct protocol is correctly implemented, and focus instead on the emerging properties across large numbers of vehicles participating in message exchanges.

While the SUMO-based simulations revealed interesting results [28], they lack formal proofs of important spatiotemporal properties. These formal verification tasks will be outlined below. We ignore the possibility of messages getting lost in transit, such as a car not meeting the predicted exit time due to a driver changing the route or taking a break. We leave this to more refined ad hoc network protocols of our future work. For simplicity, we also abstain from modelling our more advanced Context-Aware Message Flooding Protocol (CAMFLooP), which uses copies of the same message in multiple vehicles to guarantee an optimal reduction of the delivery time [28, 29]. Instead, we restrict ourselves to a prior version in which only one copy of a message is kept in the system at a time. In ad hoc networks, this message is transmitted to the network peer predicted to leave the dead spot first [26, 27].

Refer to caption — Figure 1: Simple Dead Spot Road Network with a T-intersection.

Figure 1 depicts a simple schematic dead spot, where $A$ and $B$ are two entry/exit points of the main road. The points are at the coordinates $(0,0)$ and $(100,0)$ , respectively. Further, the dead spot contains a T-intersection at point $T$ located at $(60,0)$ , in which a side road from point $C$ at $(60,20)$ joins the main road. In this scenario, we assume the car’s destination is known to the protocol in advance, like when we use Google or Apple Maps’ “Directions” features. In the following, we consider through traffic on the routes $ATB$ , $ATC$ , $BTA$ , $BTC$ , $CTA$ and $CTB$ . The blue, red, and green circles in Fig. 1 outline the positions of three cars $c_{1}$ , $c_{2}$ , and $c_{3}$ , that are all cut off from cellular network access in the depicted situation.

The trajectories of the three cars in our scenario are shown in Fig. 2. Here, car positions in the current situation (time $t_{0}=0$ ), i.e., the ones highlighted in Fig. 1, are described by filled circles. With hollow circles, we further designate the events in which vehicles leave the dead spot. We calculate the average speed through the dead spot from the time and relative distance, resulting in idealised linear car trajectories. Car $c_{1}$ travels from $A$ to $C$ in time $t_{2}$ . Car $c_{2}$ travels in the opposite direction from $T$ to $A$ in time $t_{3}$ . Car $c_{3}$ entered at $C$ and travels to $A$ from its current point $M$ in the centre between $C$ and $T$ , see Fig. 1. The cars operate at different average speeds, represented by the gradients of the lines. For instance, $c_{3}$ travels at a higher speed than $c_{2}$ , which is overtaken at point $I$ between $T$ and $A$ . At point $J$ , $c_{3}$ is passing $c_{1}$ , that runs in the opposite direction.

As described above, the dissemination protocol uses ad hoc networks to transmit messages between vehicles to speed their delivery [27]. When two cars are in relative proximity (approximately at the intersection of their respective lines on Fig. 2), they may form an ad hoc network and exchange messages to improve the anticipated message delivery time. For example, a message jumping from the blue car $c_{1}$ to the green car $c_{3}$ at about $J$ (between $A$ and $T$ ) can be delivered at the earlier exit time $t_{1}$ of $c_{3}$ rather than the later time $t_{2}$ of $c_{1}$ . The message takes the effective route $AJA$ . Likewise, the ad-hoc networks created at points $I$ and $K$ can be used to shorten the time of message deliveries.

3 Highlights of CASTeL models and logical definitions

3.1 Petri Net model variations for the dead spot scenario

3.1.1 Discrete and continuous dynamic models

The actual continuous trajectories of the cars $c_{1}$ , $c_{2}$ and $c_{3}$ may deviate from the idealised linear trajectories depicted in Fig. 2. We can imagine the accurate trajectories winding around the idealised average speed lines. If the changing speeds are known or stochastically generated in simulations, such a varying trajectory can be linearly approximated by a piecewise linear polygon. Each segment of this polygon represents the average speed of the given car on the corresponding road section. We envisage this by an equidistant segmentation of the $y$ -axis of Fig. 2, i.e., the spatial division, rather than an equidistant division on the $x$ -axis (time). This keeps with the interpretation of a Coloured Stochastic Petri Net (CSPN) as a compact discrete and continuous process generator. If the CSPN ignores the stochastic rates assigned to its transitions, one can analyse the abstract synchronization of its transitions by utilizing their net-induced partial order. The rates allow mapping any such partially ordered process onto a continuous timeline. If the specified rates are parameters in exponential distributions, the CSPN behaviour graph is equivalent to a continuous Markov chain or Markov decision process (if the CSPN is associated with reward structures), see [7]. Note that the behaviour graph of a Petri Net represents branching order or time. It forgets the spatial distribution and, therefore, the concurrency of transition firings.

Figure 3 shows parts of a CSPN for the dead spot net in Fig. 1. To describe segments of the roads in our scenario, it uses the concept of zones. For simplicity, we apply the distance of a road segment to the central point $T$ , see Fig. 1, to denominate a zone. For example, car $c_{1}$ which is at the coordinate $(1,0)$ , is $59$ units away from $T$ (coordinate $(60,0)$ ) and therefore in zone $59$ . The zones allow us to describe spatial properties, e.g., where on the road a car is or if two cars are nearby such that they can build up an ad hoc network.

Like in most PN descriptions, circles represent places and rectangles transitions. The places $\tt K$ and $\tt L$ are marked by regular tokens (colour type Dot). $\tt K$ is used to bound the number of cars allowed in the dead spot, while $\tt L$ restricts the number of messages, the cars in the dead spot may carry at maximum. In this way, it is guaranteed that our CSPN specifies only a finite number of different system states. Place $\tt Z$ contains coloured tokens representing the cars currently in the dead spot. Its tokens are marked by tuples from type $Car$ , that have the form $(f,p,t,v,m)$ and include the following elements:

•

The entrance point $f\in\{A,B,C,T\}$ , i.e. the point a car is coming from.
•

$p\in\mathbb{N}$ is an integer denoting the zone, the vehicle is currently in.
•

The exit point $t\in\{A,B,C\}$ , i.e., the point it is heading to.
•

$v\in\mathbb{N}$ is the velocity of the car.
•

$m\in\mathbb{N}$ lists the number of messages, the car carries.

In the marking shown in Fig. 3, place $\tt L$ has $M-6$ tokens. $M$ is a constant model parameter describing the maximum number of messages possible in the system. Thus, the tuple element $m$ of a token in place $\tt Z$ cannot exceed the value $M$ , i.e., $0\leq m\leq M$ . Another constant model parameter is $N$ , that bounds the number of cars allowed in the dead spot, i.e., the number of tokens in place $\tt Z$ . In the marking depicted in Fig. 3, $\tt Z$ has three colour tokens of type $Car$ . In accordance with that, place $\tt K$ has $N-3$ tokens, and More precisely, the current marking $Mrk$ (during this hypothetical simulated run) includes $Mrk(L)=M-6$ and $Mrk(K)=N-3$ , while $Mrk(Z)=\{(A,59,C,100,0),(T,0,A,80,4),(C,10,A,120,2)\}$ contains three colour tokens of type $Car$ . This marking is reached after the three cars $c_{1}$ (blue), $c_{2}$ (red) and $c_{3}$ (green) entered the dead spot by executing transition $\tt ent$ and then advanced approximately to the situation depicted in Fig. 2 (transition $\tt adv$ ). Moreover, cars $c_{2}$ and $c_{3}$ created some message payload (transition $\tt cre$ ). For each car entering the dead spot, the car capacity $\tt K$ shrinks by 1. Likewise, the message capacity $\tt L$ shrinks by 1 for each message created in the dead spot. As a car exits the dead spot (transition $\tt ext$ ), these capacities grow accordingly.

Table 1: Guards and rates for the transitions in Fig. 3.

Transition	Guard	Rate
ent	$IsRoute(f,t)\wedge f\not=T\wedge p=START(f)$	1
ext	$IsRoute(f,t)\wedge f=T\wedge p=START(t)$	1
adv	$\begin{array}[]{rl}IsRoute(f,t)\wedge&\\ ((f\not=T\wedge&\\ ((p\not=0&{\Rightarrow}\ p^{\prime}=p-1\wedge f^{\prime}=f)\>\vee\\ (p=0&{\Rightarrow}\ p^{\prime}=0\wedge f^{\prime}=T)))\>\vee\\ (f=T\wedge&p\not=START(t)\ \wedge\\ f^{\prime}=f&\wedge\ p^{\prime}=p+1\wedge t^{\prime}=t))\end{array}$	$0.04\cdot v$
cre	$true$	3
jmp	$\begin{array}[]{l}IsClose(f,p,t,f^{\prime},p^{\prime},t^{\prime})\ \wedge\\ \ \ \ \ \ \ \ \ ETA(f,p,t,v)<ETA(f^{\prime},p^{\prime},t^{\prime},v^{\prime})\end{array}$	5

3.1.2 Logical constraints and stochastic rates:

Table 1 shows the guards and rates of the transitions used for the transitions in Fig. 3. In CSPNs, guards can be interpreted dynamically as transition firing conditions or statically as conditions for unfolding the coloured net into a basic uncoloured net. A fundamental transition exists only for colour value combinations that satisfy the transition guard in the basic net. In the coloured net, the higher-level transition fires only if the required input tokens are available and their values satisfy the guard, i.e., they generate an identical reachability graph on the same reachable markings.

Moreover, we use some additional predicates and functions: $IsRoute(f,t)$ is a predicate that holds if $f$ and $t$ are different points and $t$ is an exit point of the dead spot. The function $START(f)$ indicates the initial zone position at a point $f$ . The predicate $IsClose(f,p,t,f^{\prime},p^{\prime},t^{\prime})$ is $true$ if and only if the positions of the car with the tuple colours $f$ , $p$ , and $t$ and of the one characterised by $f^{\prime}$ , $p^{\prime}$ , and $t^{\prime}$ are nearby. This accounts for cars driving in different directions, currently at different positions $p\not=p^{\prime}$ but still in direct wifi range, and so on. Finally, we use the function $ETA$ to express the expected time of arrival of a vehicle.

Rates of CSPNs are either probabilistic or they are real-valued parameters in probability density functions, for example, negative exponential functions $E(c,r,t)=c\cdot r\cdot e^{-r\cdot t}$ over time $t$ and rate $r$ , with a scaling factor $c$ . The rate function of the transition $\tt adv$ depends on the velocity $v$ of a car.

3.1.3 Parameterized component-based architecture of models:

In the initial marking (not shown in the figure), only place $\tt K$ is marked with $N$ tokens and place $\tt L$ with $M$ tokens. The current marking, depicted in the figure, is reachable from the above initial net marking. The constants $M$ and $N$ bounding the numbers of messages and the vehicles in the dead spot, respectively, are definable model parameters. Likewise, we use a constant $R$ , that expresses the number of zones into which the roads in our scenario is segmented in. Thus, our models are parameterised and give rise to a combinatorial family of nets over the possible range of these parameters. Parallel parameter sweeps [36] may result in different simulation runs with a series of stochastic plots of various model performance measurements, such as statistical frequencies of combinations of states, transitions or formulae.

CSPNs are compositional. Linear algebra methods, including products, sums, scaling, and various other operations, have been proven to underpin their composition. These operations on CSPNs can be visualized as merging the corresponding component nets by identifying some places or transitions. In Fig. 3, we illustrate this by highlighting two net components:

•

The blue subnet includes transitions for entry ( $\tt ent$ ) to and exit ( $\tt ext$ ) from the dead spot, respectively, or advancing ( $\tt adv$ ) within a zone and between adjacent zones.
•

The magenta subnet is an extension adding messaging transitions, allowing the creation ( $\tt cre$ ) of messages incrementing the message number of a car in transit; the jumping ( $\tt jmp$ ) of messages between cars in proximity transfers all messages of one car to another vehicle if that car can reach its exit faster.

As mentioned above, the properties of the dead spot mitigations protocols have already been modelled and simulated in SUMO [22] in long runs, sometimes running on several workstations or virtual machines for weeks [28]. The protocols may be extended by further features like considering the reputation of drivers (agent) with respect to keeping their planned routes and speeds or their reliability in delivering the messages after having left the dead spot. This reputation can then be used to decide which vehicle is the most reliable target for a given message. Furthermore, one can assume that some communication subscriptions support micro-payments, data entitlements, or other gratifications for drivers, so that trustworthy behaviour will also be rewarded financially. Thus, the modelling and simulation may include game-theoretic elements, where agents make ad hoc decisions regarding speed or destination with rewards in mind. Another variation provides modelling cyberattacks, where cars are hacked and behave maliciously, e.g., by offering their peers fake improvements in the message delivery when, in fact, they are discarding messages. Protocol variations offering increased fault tolerance in the presence of such attacks are of growing interest.

This raises the question of how CASTeL can feature component and product-line variation. In addition to parameters like $M$ and $N$ , colour variations are an essential means of parametrisation. For example, the combinatorial complexity of a CSPN may be managed by starting from simple models with a very limited enumeration or range type. The model can then be step-wise refined by increasing the cardinality of the colour domain, i.e., by values that change the outcome of guard evaluations. Likewise, a colour product domain may be restricted using some formulae. Conversely, conservative extensions correspond to injections. They permit some simulation between a component model and the corresponding subnet or partial composition of the system as a whole. These colour restrictions and extensions correspond to projections and injections regarding nets and their runs. Parameter variations may change a component’s qualitative and quantitative interface or execution behaviour characteristics. These may result in the inclusion or exclusion of modules in the incremental or full integration of the system.

3.1.4 Gaps:

As mentioned above, CSPN modelling and simulation have been studied in the literature, and several education and industry-strengths tools exist. However, our spatial interpretation in the CASTeL context requires extensions, explicitly identifying spatial dimensions in these nets. For example, the highlighted blue colour variables $f$ , $p$ , and $t$ (see Fig. 3) represent abstract co-ordinates in terms of distances and zone points. Thus, they are spatial variables modelling the spatial aspects in the model of the dead spot mitigation protocol.

In Petri Nets, conflicts are branches in places where sufficient tokens enable multiple transitions, which can fire mutually exclusively. In coloured nets, conflicts are resolved in one of two ways. Either the information is already contained in the marking of the net, for example, the colour values of tokens. Or conflicts are non-deterministic since information enters the system from outside, for instance, by player choices, when we use the variant with alliances sketched above. In CASTeL, player labels are particular colours, which may occur in tokens. According to the rules of the game, these are then assigned to the conflicts. A conflict between transitions must only be resolved by the players assigned to it.

3.2 Model design and logical requirement elicitation in CASTeL

The CSPN shown in Fig. 3 is a simplified discrete and abstract model for a variant of previously studied protocols [26, 27]. We assume that each car $c_{i}$ enters with a random speed $v_{i}$ chosen from a few discrete values (e.g., 80–120 km/h). It is easy to extend this variant to include variable speeds if desired. This can be easily realized by assuming, that the speed $v$ of a given car is constant in a zone, but that the transition adv may change $v$ according to simulated choices of drivers or probabilistic events abstracting from traffic uncertainties. In consequence, the vehicle may have varying speeds in the different zones, it passes.

Based on this simple formal model, that includes the creation of messages by car passengers, by IoT components for machine-to-machine (M2M) communication, or logistic tracking, we may wish to express its benefit by a precise specification, such as:

At least $p$ percent of the messages created in the dead spot arrive in less than half the time, it would take the generating car to reach the planned exit of the dead spot. Suppose furthermore $1\leq n<10$ cars out of $10$ have satellite connection and offer forwarding of messages from other cars. This improves the average time to delivery by a factor $A\cdot n+B$ , where $A$ and $B$ are constants determined by simulation runs.

Our logic CASTeL permits us to express claims like this one, including necessary spatial and temporal constraints, in an unambiguous and precise formalism. CASTeL draws elements of its syntax from different CTL-based logics and extends and reconciles them through its use of extended Generalised Stochastic Petri Nets (GSPNs) as model generators for both state-transition models and their interpretations. The use of GSPNs allow us to combine probabilistic chance with non-deterministic agent choice and reward. They are more general than models underlying, for example, ATL (Alternating-Time Temporal Logic, see [3]) and rPATL (Probabilistic Alternating-time Temporal Logic with Rewards, see [11]). In particular, stochastic rates may be real-valued time and space distributions (typically parameters in exponential distributions), for which Markovian probabilistic constraints may hold only under further constraints and normalisation. At the same time, non-Markovian PNs can be simulated statistically. PN models are not limited to alternating agent choice but can be truly concurrent. This differs from interleaving models, where concurrency is specified by allowing two agents to operate in arbitrary order but not in parallel. That is an important differentiator, especially in widely distributed systems and their performance analysis, simulation and estimation.

While the work here aims at model-checking and simulation modulo theory, our goal is also to lift necessary spatial abstractions onto an equal footing with real-time abstractions in logic based on PCTL. Such logics use bounded path formulae, in particular a logical until and unless operator with temporal bounds [16]. Such a bound limits the number of clock ticks for which a model checker checks whether safe conditions from states that might lead to hazards can be reached. In CASTeL we therefore also permit spatial bounds, which count discrete spatial steps, i.e. routes that allow mobile actors to reach spatial goals, including a safe spatial region, and reap corresponding rewards. This can be realized by bounding firing sequences $t^{n}$ of a dangling stochastic transition $t$ stochastically by the rate of $t$ , while in the underlying place-transition nets (ignoring the rates), they will be unbounded. An equivalent completion (closure) is possible by adding a place $p_{t}$ initialised with $n$ tokens. For example, we use the place K representing the maximal number $M$ of cars in the dead spot for this purpose. In this way, we guarantee a hard bound in the underlying net beside the soft bound by rates of the stochastic net.

Specifications like the one listed above make assumptions such as the following:

With a high probability (say 99%), vehicles passing each other communicate reliably while in a range of 200 meters.

Constraints are relevant for model realism, on the one hand, as we may need to exclude degenerate cases of dead spot models or car behaviour. On the other hand, constraints can avoid combinatorial explosions and unnecessary simulations of borderline cases, such as times of the day or week, when all cars travel in total isolation, times of major construction work or other hurdles, for which the protocol is not designed, or for which historical traffic data is not available. Principally, there are two kinds of constraints:

1.

Qualitative constraints using different premises. For these, our improvement formulae become conclusions. Thus, the models and theories effectively become qualitative scenarios with different or varying surrounding conditions.
2.

Quantitative constraints. Here, we use stochastic model parameters. These vary stochastic rates in CASTeL formulae. We may be able to plot behavioural observations or secondary stochastic observations as functions of varying parameter values; the variations may be discrete or continuous. We can also plug these varying parameters into the Petri Net simulation and look at the resulting variation of Petri Net properties and its provable or observed quantitative behaviour across various simulation runs.

Let us make this a little more concrete by looking at the example of “coverage bubbles” — groups of at least two collaborating cars temporarily forming an ad hoc network. In the terminology of game-theoretic logic like the Alternating Temporal Logic (ATL) [3], such collections are called alliances of players, i.e., mutually independent decision makers. To deal with mobility, CASTeL alliances are ad hoc. They form dynamically in space depending on the distance between the cars. Moreover, the vehicles operate independently, i.e., their messaging process is automated, and they move concurrently. For example, multiple pairs of cars in one or more bubbles may exchange messages while moving in and out of proximity. Likewise, players in CASTeL can make concurrent choices, such as changing their speed, adapting to traffic situations dynamically, etc. Regarding bubble formation, CASTeL assumptions may include the following:

With a significant minimal probability, say $20\%$ , the spatial density of cars allows for the formation of bubbles of at least $3$ cars somewhere in the space of the dead spot.

On the one hand, considering such assumptions in CSPN simulations limits the scenarios to be analysed by simulation runs, exploring possible processes and their stochastic properties. On the other hand, the assumptions simplify model-checking of logical guarantees required as part of requirements definitions.

Stochastic rates of car arrivals at entry points can set time intervals at the same space point, i.e., bounds for the average space-time density across a dead spot. Following the concept of Multi-hop Cellular Network (MCN) [23], in which a mobile unit communicates with a fixed base station utilizing others as relay stations, the proximity relation between cars may define a connected graph for a crowded dead spot. This graph is the support of the coverage bubble. Messages inside a coverage bubble can exit by a sequence of hops at a speed limited by communication speed and the number of hops required. An example scenario is depicted in Fig. 4. Here, the ad hoc network connections between the five vehicles $c_{1}$ to $c_{5}$ (solid ellipses) form a coverage bubble, which is visualized as a dotted ellipse. This makes it possible that, e.g., messages stored in $c_{1}$ can be forwarded via some other vehicles acting as relay stations to $c_{5}$ , which is outside the dead spot and can forward the messages via the cellular network.

The time of a single hop is dominated by the time it takes to establish a connection or switch from one to another. Furthermore, it depends on message lengths. Since the density of cars may vary, coverage bubbles may not connect directly to the dead spot exit. Moreover, a bubble may disintegrate fast when its support cars travel in opposing directions, e.g., in Fig. 4 cars $c_{2}$ and $c_{3}$ move in the opposite direction of all the other cars and will soon be out of range. Then, $c_{1}$ cannot form a bubble with $c_{4}$ and $c_{5}$ anymore. However, a group of vehicles travelling in the same direction at similar speeds may maintain a coverage bubble for an extended period, e.g., $c_{2}$ and $c_{3}$ .

3.2.1 Gaps

Like for models, the CASTeL logical specification requires extensions to the logics it builds upon. Firstly, our PCTL-like formulae use a bounded until operator. While this is sufficient for iterative time bounds, CASTeL also needs spatial bounds for iterating over space. For example, when reasoning inductively about vehicle routes, one may specify that cars will reach their planned destination based entirely on the road network’s structure and spatial decisions. Secondly, players in alliances may resolve conflicts concurrently, and reward structures may be associated with alliances or individual players. Thirdly, alliances may be ad hoc. For example, bubbles of vehicles in proximity form such alliances. To this end, ATL-like formulae using the enforceability operator must be allowed to range over ad hoc alliances. To this end, we use player sets constrained by predicates like the $IsClose$ predicate used in Table 1.

4 Related Work

Stochastic reward PNs have been used prior in the work of Chiola et al. [12] and Marsan et al. [2]. Their main objective was modelling close to the domain-specific informal models of practitioners, their quantitative reliability estimates, and risk management requirements. However, while methods to specify external events and risks were included, those to describe security risks such as cyber-attacks were not. The approach formed a basis for the creation of the GreatSPN tool for the stochastic analysis of systems modelled as (stochastic) PNs, see [6, 13]. Heiner et al. introduced a comparative study of stochastic analysis techniques in [18]. Part of their approach was the tool Snoopy to model and simulate hierarchical graph-based system descriptions, see [17]. It allows users to analyse several kinds of PNs, including timed PNs and stochastic PNs.

The probabilistic model checker Storm was introduced in [15, 19]. Storm supports the analysis of discrete- and continuous-time variants of both Markov chains and Markov decision processes (MDPs). Open-source Storm methods and tools are used in the backend of GreatSPN and PRISM.

Spatio-temporal models for formal analysis and property-based testing were presented in [4, 33]. These works focus on supporting software engineers in understanding temporal models (making formal representations more accessible to the industrial application). Moreover, they provide a schematic translation of time-based constructs to the spatial analyser BeSpaceD [10]. Another approach to model spatial aspects of safety-critical systems was presented in [33]. That work applies the formal language Focus^ST and presents an example system based on interacting autonomous vehicles.

In our previous work on BSpaceD [20, 21], we have used theorem-proving modulo theory based on the Microsoft SMT prover Z3 [9] applied to industrial robotics and autonomous vehicles, such as collision avoidance in a primarily automated fulfilment centre. Space-time-related algorithms were written in Scala and check the satisfiability of speed-dependent safe spatiotemporal separation of any pair of mobile autonomous objects in proximity, including robot-to-robot movement or mobile robots in safe separation from human staff and movement.

5 Conclusion and Future work

This paper presented an overview of CASTeL, a Concurrent Alliances Spatio-Temporal Logic. We illustrated it by a motivating scenario, in which we model an opportunistic mobile ad-hoc network formed by the cars or trucks crossing a communication dead spot and analyse possible variations.

The CASTeL approach builds on the marriage of elements from PCTL and ATL with reward structures and model-checked using concurrent Petri Nets, particularly Coloured Generalised Stochastic Petri Nets (GSPN). CASTeL stands apart from other temporal logics by providing extensions for spatial abstractions and spatially stochastic distributions. The concurrent interpretation of players (decision makers) enables reasoning and analyses about the collaboration within alliances and competition between them. Furthermore, the modelling focuses on system-level properties, which emerge from the interaction of the system components in the context of many concurrent individual failures, misbehaviours or malicious actions. We motivated these novel extensions with a mobile ad hoc network example and showed how dynamic alliance formation can be modelled. Moreover, we outlined how emergent safety and security properties can be guaranteed by model-checking within stochastic bounds using existing tools or suggested extensions. Our work uses backend tools with well-documented scalability limitations, in particular stochastic model-checkers and Petri net tools.

Future Work: Our future work will focus on detailed presentation of the CASTeL semantics and performance evaluations to help prioritise backend extensions aiming to relax limitations. One of the directions to evolve CASTeL is to cover scenarios where speeds vary arbitrarily by player choices, potentially due to road or traffic conditions. We already modelled the spatio-temporal resolution using model parameters (constants) and can therefore generate a sequence of models of finer granularity and plot the increasingly refined approximations of continuous models. Another direction is to consider the behaviour of drivers in an ad hoc alliance, and to classify them into categories such as cooperative, uncommitted or adversarial, corresponding to their willingness to deliver messages when exiting dead spots. This may include consideration of the relative rates of each type, such as in say 20 vehicles, there are expected to be 12 cooperative drivers, 7 uncommitted and 1 adversarial. In addition, one could consider the relative probabilities of cooperative, uncommitted and adversarial behaviour across sparse versus dense areas, or according to the number of vehicles in a given area.

In a future refined model, (i) the average speed may vary during a simulation run, for example, by the hour of the day and the day of the year, and (ii) the speed at a location may be varied for different cars, by adding additional token colours to a car (such as some proxy for speed: slow, moderate, fast or speeding).

Recent research has used machine learning to determine or fine-tune the rates in stochastic Petri Nets. About CASTeL and its underlying CSPN models, there are two promising approaches. Firstly, machine learning may assist in reducing the complexity of the reachability problem [30], permitting relatively fast simulation and model-checking by trading off accuracy about rare events. Secondly, AI learning of Markov processes has been applied to stochastic Petri Nets based on their reachability graphs when these are Markovian [25, 34]. Then, machine-learning methods for Markov models and decision processes can be applied directly. However, non-Markovian reachability graphs reflect some history sensitivity. Large language models may capture sufficient history in the current state, i.e. via additional states and weights of their outgoing transitions.

References

[1] Ahmed, K., Blech, J.O., Gregory, M.A., Schmidt, H.: Software defined networking for communication and control of cyber-physical systems. In: 2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS). pp. 803–808. IEEE (2015)
[2] Ajmone Marsan, M., Balbo, G., Bobbio, A., Chiola, G., Conte, G., Cumani, A., et al.: On Petri nets with stochastic timing. In: Timed Petri Nets, pp. 80–87. IEEE Computer Society Press (1985)
[3] Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM (JACM) 49(5), 672–713 (2002)
[4] Alzahrani, N., Spichkova, M., Blech, J.O.: Spatio-temporal models for formal analysis and property-based testing. In: Software Technologies: Applications and Foundations: STAF 2016 Collocated Workshops: Revised Selected Papers. pp. 196–206. Springer (2016)
[5] Amanullah, M.A., Loke, S.W., Baruwal Chhetri, M., Doss, R.: A taxonomy and analysis of misbehaviour detection in cooperative intelligent transport systems: A systematic review. Acm Computing Surveys 56(1) (Aug 2023)
[6] Amparore, E.G., Balbo, G., Beccuti, M., Donatelli, S., Franceschinis, G.: 30 years of GreatSPN. Principles of Performance and Reliability Modeling and Evaluation: Essays in Honor of Kishor Trivedi on his 70th Birthday pp. 227–254 (2016)
[7] Baarir, S., Beccuti, M., Cerotti, D., De Pierro, M., Donatelli, S., Franceschinis, G.: The GreatSPN tool: recent enhancements. ACM SIGMETRICS Performance Evaluation Review 36(4), 4–9 (2009)
[8] Bennaceur, A., Ghezzi, C., Tei, K., Kehrer, T., Weyns, D., Calinescu, R., Dustdar, S., Hu, Z., Honiden, S., Ishikawa, F., Jin, Z., Kramer, J., Litoiu, M., Loreti, M., Moreno, G., Müller, H., Nenzi, L., Nuseibeh, B., Pasquale, L., Reisig, W., Schmidt, H., Tsigkanos, C., Zhao, H.: Modelling and analysing resilient cyber-physical systems. In: 2019 IEEE/ACM 14th International Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS). pp. 70–76 (2019)
[9] Bjørner, N., Eisenhofer, C., Kovács, L.: Satisfiability modulo custom theories in Z3. In: Dragoi, C., Emmi, M., Wang, J. (eds.) Verification, Model Checking, and Abstract Interpretation. pp. 91–105. Springer Nature Switzerland, Cham (2023)
[10] Blech, J.O., Schmidt, H.: BeSpaceD: Towards a Tool Framework and Methodology for the Specification and Verification of Spatial Behavior of Distributed Software Component Systems. Tech. Rep. 1404.3537, arXiv.org (2014)
[11] Chen, T., Forejt, V., Kwiatkowska, M., Parker, D., Simaitis, A.: Automatic verification of competitive stochastic systems. Formal Methods in System Design 43, 61–92 (2013)
[12] Chiola, G.: A software package for the analysis of generalized stochastic Petri net models. In: International Workshop on Timed Petri Nets. p. 136–143. IEEE Computer Society, USA (1985)
[13] Chiola, G., Franceschinis, G., Gaeta, R., Ribaudo, M.: Greatspn 1.7: Graphical editor and analyzer for timed and stochastic Petri nets. Performance evaluation 24(1-2), 47–68 (1995)
[14] Clarke, E.M., Emerson, E.A.: Design and Synthesis of Synchronisation Skeletons using Branching Time Temporal Logic. In: Workshop on the Logic of Programs. pp. 52–71. No. LNCS 131, Springer-Verlag, Berlin (1981)
[15] Dehnert, C., Junges, S., Katoen, J.P., Volk, M.: A storm is coming: A modern probabilistic model checker. In: Computer Aided Verification: 29th International Conference (CAV). pp. 592–600. Springer (2017)
[16] Hansson, H., Johnsson, B.: A logic for reasoning about time and reliability. Formal aspects of computing 6(5), 512–535 (1994)
[17] Heiner, M., Richter, R., Schwarick, M.: Snoopy: a tool to design and animate/simulate graph-based formalisms. In: Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops. pp. 1–10 (2008)
[18] Heiner, M., Rohr, C., Schwarick, M., Streif, S.: A comparative study of stochastic analysis techniques. In: Proceedings of the 8th International Conference on Computational Methods in Systems Biology. pp. 96–106 (2010)
[19] Hensel, C., Junges, S., Katoen, J.P., Quatmann, T., Volk, M.: The probabilistic model checker Storm. International Journal on Software Tools for Technology Transfer pp. 1–22 (2022)
[20] Herrmann, P., Blech, J.O.: Formal analysis of control software for cyber-physical systems. In: 2017 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-c). pp. 563–564 (2017)
[21] Herrmann, P., Blech, J.O., Han, F., Schmidt, H.: Model-based development and spatiotemporal behavior of cyber-physical systems. In: Innovative Solutions and Applications of Web Services Technology, pp. 69–93. IGI Global (2019)
[22] Krajzewicz, D.: Traffic simulation with SUMO simulation of urban mobility. In: Fundamentals of Traffic Simulation, International Series in Operations Research & Management Science, vol. 145, pp. 269–293. Springer, United States (2010)
[23] Lin, Y.D., Hsu, Y.C.: Multihop Cellular: A New Architecture for Wireless Communications. In: IEEE INFOCOM, Conference on Computer Communications. vol. 3, pp. 1273–1282 (2000)
[24] Lopez, P.A., Behrisch, M., Bieker-Walz, L., Erdmann, J., Flötteröd, Y.P., Hilbrich, R., Lücken, L., Rummel, J., Wagner, P., Wießner, E.: Microscopic Traffic Simulation using SUMO. In: IEEE Intelligent Transportation Systems Conference (ITSC). pp. 2575–2582. IEEE (2018)
[25] Mao, H., Liu, Z., Qiu, C.: Adaptive disassembly sequence planning for VR maintenance training via deep reinforcement learning. International journal of advanced manufacturing technology 124(9), 3039–3048 (2023)
[26] Meyer, J.A.E., Puka, E., Herrmann, P.: Utilizing Connectivity Maps to Accelerate V2I Communication in Cellular Network Dead Spots. In: 6th International Conference on Internet of Vehicles (IOV). pp. 76–87. No. 11894 in LNCS, Springer-Verlag, Kaohsiung, Taiwan (2019)
[27] Puka, E., Herrmann, P.: Data Dissemination for Vehicles in Temporary Cellular Network Dead Spots. International Journal of Cyber-Physical Systems (IJCPS) 1(2), 38–55 (2019)
[28] Puka, E., Herrmann, P.: Simulating a Context-Aware Message Flooding Protocol to Mitigate Cellular Dead Spots with Realistic Drivers’ Behavior. In: 24th IEEE International Conference on Intelligent Transportation (ITSC). pp. 1041–1048. IEEE, Indianapolis, IN, USA (Sep 2021)
[29] Puka, E., Herrmann, P., Taherkordi, A.: Hybrid Context-aware Message Flooding for Dead Spot Mitigation in V2I Communication. In: 92nd IEEE Vehicular Technology Conference (VTC-Fall). pp. 1–7. IEEE VTS, Victoria, BC, Canada (2020)
[30] Qi, H., Guang, M., Wang, J., Yan, C., Jiang, C.: Probabilistic reachability prediction of unbounded Petri nets: A machine learning method. IEEE transactions on automation science and engineering pp. 1–13 (2023)
[31] Schmidt, H., Spichkova, M.: Towards readability aspects of probabilistic mode automata. In: Proceedings of the 14th International Conference on Evaluation of Novel Approaches to Software Engineering. pp. 555–562 (2019)
[32] Schmidt, H.W., Peake, I., Aysan, H.A., Punnekkat, S., Dobrin, R.: Towards probabilistic mode automata for adaptable resource-aware component-based systems design. In: Proceedings of the International Improoving Systems and Software Engineering Conference (2012)
[33] Spichkova, M., Blech, J.O., Herrmann, P., Schmidt, H.: Modeling spatial aspects of safety-critical systems with focus-st. In: MoDeVVa’14. pp. 49–58. Springer (2014)
[34] Vanson, G., Marangé, P., Levrat, E.: End-of-Life Decision making in circular economy using generalized colored stochastic Petri nets. Autonomous intelligent systems 2(1), 1–18 (2022)
[35] Wi-Fi Alliance, P2P Technical Group: Wi-Fi Peer-to-Peer (P2P) Technical Specification v1.7 (2016)
[36] Yusuf, I.I., Schmidt, H.W., Thomas, I.E., Spichkova, M., Androulakis, S., Meyer, G.R., Drumm, D.W., Opletal, G., Russo, S.P., Buckle, A.M.: Chiminey: Reliable computing and data management platform in the cloud. In: 37th IEEE International Conference on Software Engineering. vol. 2, pp. 677–680. IEEE (2015)