Bigraphs are a versatile modelling formalism that allows easy expression of placement and connectivity relations in a graphical format. System evolution is user defined as a set of rewrite rules. This article presents a practical, yet detailed guide to developing, executing, and reasoning about bigraph models, including recent extensions such as parameterised, instantaneous, prioritised and conditional rules, and probabilistic and stochastic rewriting.

Abstract Belief–desire–intention (BDI) agents are a popular agent architecture. We extend conceptual agent notation (Can)—a BDI programming language with advanced features such as failure recovery and declarative goals—to include probabilistic action outcomes, e.g. to reflect failed actuators, and probabilistic policies, e.g. for probabilistic plan and intention selection. The extension is encoded in Milner’s bigraphs. Through application of our BigraphER tool and the PRISM model checker, theprobabilityof success (intention completion) under different probabilistic outcomes and plan/event/intention selection strategies can be investigated and compared. We present a smart manufacturing use case. A significant result is that plan selection has limited effect compared with intention selection. We also see that the impact of action failures can be marginal—even when failure probabilities are large—due to the agent making smarter choices.

The Belief-Desire-Intention (BDI) architecture is a popular framework for rational agents, yet most verification approaches are limited to analysing the behaviours of an agent in a subset of all possible environments.However, in practice, BDI agents operate in dynamic environments where the exact occurrence of external changes is difficult to predict.For safety/security we need to assess whether the agent behaves as required in all circumstances.To address this, we define environments, accounting for both sensor information about physical changes and new tasks to be completed, as a non-deterministic finitestate automata.We give an environment-enabled extension to the Conceptual Agent Notation (CAN) language including an executable semantics via an encoding to Milner's bigraphs and the BigraphER tool.We illustrate the framework through a simple Unmanned Aerial Vehicle (UAV) example that is verified using mainstream tools including PRISM model checker.Results show our approach can automatically identify agent design flaws to aid agent programmers in design, debugging, and analysis.

Bigraphs are a universal computational modelling formalism for the spatial and temporal evolution of a system in which entities can be added and removed. We extend bigraphs to probabilistic bigraphs, and then again to action bigraphs, which include non-determinism and rewards. The extensions are implemented in the BigraphER toolkit and illustrated through examples of virus spread in computer networks and data harvesting in wireless sensor systems. BigraphER also supports the existing stochastic bigraphs extension of Krivine et al. and using BigraphER we give, for the first time, a direct implementation of the membrane budding model used to motivate stochastic bigraphs.

When a component fails in a critical communications service, how urgent is a repair? If we repair within 1 hour, 2 hours, or$n$hours, how does this affect the likelihood of service failure? Can a formal model support assessing the impact, prioritisation, and scheduling of repairs in the event of component failures, and forecasting of maintenance costs? These are some of the questions posed to us by a large organisation and here we report on our experience of developing a stochastic framework based on a discrete space model and temporal logic to answer them. We define and explore both standard steady-state and transient temporal logic properties concerning the likelihood of service failure within certain time bounds, forecasting maintenance costs, and we introduce a new concept ofenvelopes of behaviourthat quantify the effect of the status of lower level components on service availability. The resulting model is highly parameterised and user interaction for experimentation is supported by a lightweight, web-based interface.

Large-scale wireless sensor networks (WSN) are increasingly deployed and an open question is how they can support multiple applications. Networks and sensing devices are typically heterogeneous and evolving: topologies change, nodes drop in and out of the network, and devices are reconfigured. The key question we address is how to verify that application requirements are met, individually and collectively, and can continue to be met, in the context of large-scale, evolving network and device configurations. We define a modelling and verification framework based on Bigraphical Reactive Systems (BRS) for modelling, with bigraph patterns and temporal logic properties for specifying application requirements. The bigraph diagrammatic notation provides an intuitive representation of concepts such as hierarchies, communication, events and spatial relationships, which are fundamental to WSNs. We demonstrate modelling and verification through a real-life urban environmental monitoring case-study. A novel contribution is automated online verification using BigraphER and replay of real-life sensed data streams and network events by the Cooja network simulator. Performance results for verification of two application properties running on a WSN with up to 200 nodes indicate our framework is capable of handling WSNs of that scale.

While HCI has a long tradition of formally modelling task-based interactions with graphical user interfaces, there has been less progress in modelling emerging ubiquitous computing systems due in large part to their highly contextual nature and dependence on unreliable sensing systems. We present an exploration of modelling an example ubiquitous system, the Savannah game, using the mathematical formalism of bigraphs, which are based on a universal process algebra that encapsulates both dynamic and spatial behaviour of autonomous agents that interact and move among each other, or within each other. We establish a modelling approach based on four perspectives on ubiquitous systems—Computational, Physical, Human, and Technology—and explore how these interact with one another. We show how our model explains observed inconsistencies in user trials of Savannah, and then, how formal analysis reveals an incompleteness in design and guides extensions of the model and/or possible system re-design to resolve this.

Bigraphical Reactive Systems (BRS) were designed by Milner as a universal formalism for modelling systems that evolve in time, locality, co-locality and connectivity. But the underlying model of location (the place graph) is a forest, which means there is no straightforward representation of locations that can overlap or intersect. This occurs in many domains, for example in wireless signalling, social interactions and audio communications. Here, we define bigraphs with sharing, which solves this problem by an extension of the basic formalism: we define the place graph as a directed acyclic graph, thus allowing a natural representation of overlapping or intersecting locations. We give a complete presentation of the theory of bigraphs with sharing, including a categorical semantics, algebraic properties, and several essential procedures for computation: bigraph with sharing matching, a SAT encoding of matching, and checking a fragment of the logic BiLog. We show that matching is an instance of the NP-complete sub-graph isomorphism problem and our approach based on a SAT encoding is also efficient for standard bigraphs. We give an overview of BigraphER (Bigraph Evaluator & Rewriting), an efficient implementation of bigraphs with sharing that provides manipulation, simulation and visualisation. The matching engine is based on the SAT encoding of the matching algorithm. Examples from the 802.11 CSMA/CA RTS/CTS protocol and a network management support system illustrate the applicability of the new theory.

Abstract Stochastic bigraphical reactive systems (SBRS) is a recent formalism for modelling systems that evolve in time and space. However, the underlying spatial model is based on sets of trees and thus cannot represent spatial locations that are shared among several entities in a simple or intuitive way. We adopt an extension of the formalism, SBRS with sharing , in which the topology is modelled by a directed acyclic graph structure. We give an overview of SBRS with sharing, we extend it with rule priorities, and then use it to develop a model of the 802.11 CSMA/CA RTS/CTS protocol with exponential backoff, for an arbitrary network topology with possibly overlapping signals. The model uses sharing to model overlapping connectedness areas, instantaneous prioritised rules for deterministic computations, and stochastic rules with exponential reaction rates to model constant and uniformly distributed timeouts and constant transmission times. Equivalence classes of model states modulo instantaneous reactions yield states in a CTMC that can be analysed using the model checker PRISM. We illustrate the model on a simple example wireless network with three overlapping signals and we present some example quantitative properties.

Home wireless networks are difficult to manage and comprehend because of evolving locality, co-locality, connectivity and interaction. We define formal models of home wireless network infrastructure and policies and investigate how they can be used in a network management system designed to provide user-oriented support. We model spatial and temporal behaviour of network interactions and user-initiated network policies and define an online framework for generation of models from network and user-initiated events. The models are expressed in an extension to Milnerʼs bigraphical reactive systems. Analysis of the models is carried out in real-time by a bespoke bigraph reasoning system based on checking predicates, which is encoded as bigraph matching. Real-time model generation and analysis is implemented on the experimental Homework system router and trialled with synthetic and actual network data.

Abstract. We describe how the tree identification phase of the IEEE 1394 high-performance serial bus (FireWire) protocol is modelled in Promela and verified using SPIN. The verification of arbitrary system configurations is discussed.

The automatic verification of concurrent systems by model-checking is limited due to the inability to generalise results to systems consisting of any number of processes. We use abstraction to prove general results, by model-checking, about feature interaction analysis of a telecommunications service involving any number of processes. The key idea is to model-check a system of constant number (m) of concurrent processes, in parallel with an "abstract" process which represents the product of any number of other processes. The system, for any specified set of selected features, is generated automatically using Perl scripts.

Symbolic transition systems separate data from process behaviour by allowing the data to be uninstantiated. Designing an HML-like modal logic for these transition systems is interesting because of the subtle interplay between the quantifiers for the data and the modal operators (quantifiers on transitions). This paper presents the syntax and semantics of such a logic and discusses the design issues involved in its construction. The logic has been shown to be adequate with respect to strong early bisimulation over symbolic transition systems derived from Full LOTOS. We define what is meant by adequacy and discuss how we can reason about it with the aid of a mechanized theorem prover.