The Bigraphical Model

Bigraphs are a rigorous generic model for systems of autonomous agents that interact and move among each other, or within each other. They can be specialised to very different applications. In particular, they offer a unified platform for ubiquitous systems. They are proposed as a Ubiquitous Abstract Machine, playing the foundational role for ubiquitous computing that the von Neumann machine has played for sequential computing.

Bigraphs have evolved from process calculi, especially the calculus of Mobile Ambients (invented by L Cardelli and A Gordon) and the Pi calculus. Over-simplifying a little, the Ambient calculus models spatial reconfiguration, while the Pi calculus models reconfiguration of connectivity. Ubiquitous systems need both. Bigraphs allow agents to be structured simultaneously in these two ways (hence the `bi' prefix); the two structures are independent, so that where you are does not dictate whom you talk to. This independence has led to an elegant theory.

To specialise Bigraphs to a particular family of systems, we impose a sorting discipline. This declares specific sorts of nodes and edges for the graphs, and may also impose a formation rule that limits the admissible graphs. By this means, Bigraphs have been specialised to represent existing process calculi, recovering their specific theories by means of its generic theory. Bigraphs can also be specialised to such different applications as the movement of agents (e.g. humans) in a built environment and the behaviour of cells and molecules in biology.

Through their graphical presentation, Bigraphs can make it easy for non-experts to visualise their system and assemble them geometrically. Through their algebraic representation they allow the derivation of languages for programming and simulation.

Learning about Bigraphs

This website is linked to my book, The Space and Motion of Communicating Agents [1], published in March 2009 by Cambridge University Press. It emphasizes the evolution of Bigraphs from their antecedent process calculi. It presents the theory rigorously, and demonstrates how particular calculi can be represented in Bigraphs. There is a Commentary on aspects of the book; a link to it appears below [2]. It includes a list of corrections, and I hope to keep it up-to-date.

The book was written in parallel with work by the Bigraphical Programming Languages research group [3] at the IT University in Copenhagen. They have explored aspects of the theory, and developed prototype implementations, anticipating the need for software tools to mediate the theory to designers.

The book is self-contained, but some who wish to learn about Bigraphs may like to begin with a less detailed account. This is provided by the Slides for a course of six Lectures [4], highlighting the main ideas with examples, without too many definitions and theorems. These Slides are accompanied by Lecture Notes [5]: a sequence of slide-by-slide comments that also refer directly to relevant parts of the book. There is a set of Exercises [6] associated with each lecture, complete with Solutions [7]. There is also a set of Notes [8] for six seminars, on theoretical developments prompted by discussions on the applications of bigraphs; they will first be given in the Informatics Forum at Edinburgh University in a two days workshop October 13/14 2009. Finally, there is a short Bibliography [9] of papers.

Without serious experiment a theory such as this cannot be definitive. The present state of Bigraph model is the result of much revision and is rather stable. This website aims to encourage tool-building and large-scale experiment with the model, pointing the way for its future development. I would therefore welcome comments of any kind, or proposals for tool-building. Please send them to me at rm135-at-cam.ac.uk, or contact the BPL research group at ITU Copenhagen.

References

  1. The Space and Motion of Communicating Agents. Cambridge University Press, March 2009.
    Read the Prologue.
  2. Commentary for the book, including corrections.
  3. Bigraphical Programming Languages.. Laboratory for Context-dependent Mobile Communication, IT University, Denmark.
  4. Bigraphs: a model for mobile agents. Slides for a course of six lectures on bigraphs, given first at the Laser Summer School in Elba, directed by Bertrand Meyer, September 2008.
  5. Notes for the Lectures.
  6. Exercises for the Lectures
  7. Solutions for the Exercises
  8. Seminar Notes on developments in Bigraphs -- updated 27 November '09.
  9. A short Bibliography for Bigraphs

A larger bibliography is maintained by Mikkel Bundgaard.