Modelling Real-time Systems with Bigraphs

Maram Albalwe, Blair Archibald Michele Sevegnani · 2025

Read Modelling Real-time Systems with Bigraphs by Maram Albalwe, Blair Archibald Michele Sevegnani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13449.txt.

Introduction

Maram Albalwe, Blair Archibald, and Michele Sevegnani extend a graph-based modeling method so it can handle real-time systems, in a 2025 paper. The method, built on bigraphs, describes systems that change both in space and in links, like a person in a room or phones in contact.

Until now the method had no sense of time. The authors add digital clocks drawn from several viewpoints, so a model can show time passing between actions. Their setup lets each state offer a choice: let time pass, or act now. They built the approach in an existing toolkit and tested it on examples, including cloud system requests. The work opens the method to deadlines and timed behavior.

Catalog record

CREATORMaram Albalwe, Blair Archibald Michele Sevegnani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-13449

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Modelling Real-time Systems with Bigraphs Maram Albalwe, Blair Archibald Michele Sevegnani Abstract Bigraphical Reactive Systems (BRSs) are a graph-rewriting formalism describing systems evolving in two dimensions: spatially, e.g. a person in a room, and non-spatially, e.g. mobile phones communicating regardless of location. Despite use in domains including communication protocols, agent programming, biology, and security, there is no support for real-time systems. We extend BRSs to support real-time systems with a modelling approach that uses multiple perspectives to represent digital clocks. We use Action BRSs, a recent extension of BRSs, where the resulting transition system is a Markov Decision Process (MDP). This allows a natural representation of the choices in each system state: to either allow time to pass or perform a specific action. We implement our proposed approach using the BigraphER toolkit, and demonstrate the effectiveness through multiple examples including modelling cloud system requests. 1 Introduction Bigraphs are a computational model where systems are described based on two types of relationships: spatially using nesting (and parallel adjacency) and non-local linking through hyperlinks regardless of locations. Like standard graphs, bigraphs have an equivalent diagrammatic and algebraic representation. Bigraphical Reactive Systems (BRSs) equip bigraphs with a set of reaction rules that specify how a system evolves over time, i.e. reaction rules substitute sub-bigraphs with other bigraphs. The standard theory of bigraphs has been extended to model a wider range of systems e.g. stochastic bigraphs [ 12 ] assign rates to reaction rules, bigraphs with sharing [ 22 ] allow intersecting locations, directed bigraphs [ 9 ] associate directions to links, conditional bigraphs [ 3 ] add conditions to rules, and probabilistic and action bigraphs [ 4 ] support probabilistic and non-deterministic behaviour. Using these extensions, bigraphs have been successfully used to model a variety systems including mixed-reality games [ 7 ] , cloud systems [ 20 ] , self-adaptive fog systems [ 21 ] , sensor network infrastructure [ 24 ] , and rational agents [ 5 ] . An extension that has not been explored is real-time bigraphs that can model systems exhibiting non-deterministic behaviour that is controlled by time constraints. While the non-deterministic aspects of real-time systems could be modelled by action bigraphical reactive systems (ABRSs) in which the underlying Markov Decision Process (MDP) semantics allows for a transition choice at each state, there is currently no notion of clock constraints in the theory, e.g. specifying that after 3 time units have passed, a given action must occur. We propose a modelling strategy to encode timed systems within ABRSs through the well-known MDP-based digital clock approximation. We introduce a clock, as a new bigraph entity, for each timed entity in the system and we place these in a separate region so all the clocks can be manipulated without polluting the actual system model. This allows one reaction rule to advance all clocks at once, and this reduces the state space overhead of the approach. We mirror the real-time passage by introducing a global clock that controls the system execution time, i.e. system terminates when we reach the time limit of this clock, and we explicitly model the non-deterministic behaviour, i.e. at each state there is a choice between taking an action or allowing time to pass when the constraints are not yet satisfied. We make the following research contributions: • We propose a modelling strategy to express clocks within action bigraphs. • We define a set of reaction rules to model clock constraints in real-time systems through a digital clocks approximation. • We illustrate how to use our approach in practice by partially modelling the timed aspects of a cloud computing scenario. • We implement this approach in BigraphER [ 23 ] to show this is not just a theoretical contribution, but a practical one. Outline. We give an informal description of bigraphs and BRSs in Section 2 . Section 3 provides a description of non-deterministic models and shows how to formalise digital clocks within ABRSs. We illustrate our approach by providing a BRS implementation for a simple scenario modelled as a (probabilistic) timed automaton and a model of cloud system requests in Section 4 . Section 5 gives a brief literature review, and we conclude in Section 6 . \mathtt{A} \mathtt{B} \mathtt{C} (a) Data Active Active ID ( A ) ID ( B ) ID ( C ) S S S (b) Figure 1 : (a) Example network topology with three sensors; (b) corresponding bigraph with data to be transmitted by sensor A and the status of each sensor ( e.g. Active). 2 Background 2.1 Bigraphs Introduced by Milner [ 17 ] , Bigraphs provide a powerful diagrammatic representation for modelling systems that evolve in both spatial and non-spatial dimensions. Bigraphs represent the structure of a system through two relations over its entities: a place graph that encodes their spatial arrangement, e.g. a person in a room, and a link graph that specifies, through hyper-edges, non-spatial relations, e.g. communication capabilities between network devices. We give an informal description of bigraphs using the example in Figure 1 . A comprehensive formal description can be found elsewhere [ 17 ] . Bigraphs have both a diagrammatic representation and equivalent algebraic notation. We use the diagrammatic notion throughout this paper. Figure 1(a) shows a simple network topology consisting of three sensors connected to each other by communication links. Data may be exchanged between two sensors when the receiver is active. A corresponding bigraph representation is in Figure 1(b) . Sensors are represented as entities of type S that have nested identifiers (also just a different type of entity) \textsf{ID}(\mathtt{A}) , \textsf{ID}(\mathtt{B}) , and \textsf{ID}(\mathtt{C}) . The sender contains an entity Data that can be sent to other sensors when they are in the Active mode. We sometimes draw different entity types by using different shapes or colours e.g. we have used squares for identifiers and a circles for Data . Entities can be atomic , e.g. Data , meaning they have no children, or contain any number of other entities. We allow entities to be parameterised to represent families of entities, i.e. \textsf{ID}(x) specifies a new entity for every possible value of x (which may be string, integer, or float typed). Sites—filled dashed rectangles—represent unspecified bigraphs: an arbitrary bigraph, including the empty bigraph, might exist there. Bigraphs may consist of more than one region—clear dashed rectangles—which represent adjacent parts of the system. For the link graph, entities have a fixed arity that represents the number of links they must have (the green edges). Links are hyperlinks that may connect 1 -to- n . Open links—a link that has a name— indicates a link that may connect elsewhere, i.e. to currently unspecified entities. Links may also be closed, a 1 -to- 0 hyperedge, which is shown by an orthogonal line at the end of the link. Open names, sites, and regions allow model composition: regions of one bigraph can be placed in the sites of another and like-names joined. This forms the basis of the rewriting theory. 2.2 Bigraphical Reactive Systems (BRSs) A bigraph represents a system at a single point in time. To model dynamic behaviour, Bigraphical Reactive Systems (BRSs) equip bigraphs with a set of reaction rules specifying how the system

Read the complete text