The Pi Calculus: Towards Global Computing

4 April, 2019

 

Check out the video of Christian Williams’’s talk in the Applied Category Theory Seminar here at U. C. Riverside. It was nicely edited by Paola Fernandez and uploaded by Joe Moeller.

Abstract. Historically, code represents a sequence of instructions for a single machine. Each computer is its own world, and only interacts with others by sending and receiving data through external ports. As society becomes more interconnected, this paradigm becomes more inadequate – these virtually isolated nodes tend to form networks of great bottleneck and opacity. Communication is a fundamental and integral part of computing, and needs to be incorporated in the theory of computation.

To describe systems of interacting agents with dynamic interconnection, in 1980 Robin Milner invented the pi calculus: a formal language in which a term represents an open, evolving system of processes (or agents) which communicate over names (or channels). Because a computer is itself such a system, the pi calculus can be seen as a generalization of traditional computing languages; there is an embedding of lambda into pi – but there is an important change in focus: programming is less like controlling a machine and more like designing an ecosystem of autonomous organisms.

We review the basics of the pi calculus, and explore a variety of examples which demonstrate this new approach to programming. We will discuss some of the history of these ideas, called “process algebra”, and see exciting modern applications in blockchain and biology.

“… as we seriously address the problem of modelling mobile communicating systems we get a sense of completing a model which was previously incomplete; for we can now begin to describe what goes on outside a computer in the same terms as what goes on inside – i.e. in terms of interaction. Turning this observation inside-out, we may say that we inhabit a global computer, an informatic world which demands to be understood just as fundamentally as physicists understand the material world.” — Robin Milner

The talks slides are here.

Reading material:

• Robin Milner, The polyadic pi calculus: a tutorial.

• Robin Milner, Communicating and Mobile Systems.

• Joachim Parrow, An introduction to the pi calculus.


Social Contagion Modeled on Random Networks

29 March, 2019

 

Check out the video of Daniel Cicala’s talk, the fourth in the Applied Category Theory Seminar here at U. C. Riverside. It was nicely edited by Paola Fernandez and uploaded by Joe Moeller.

Abstract. A social contagion may manifest as a cultural trend, a spreading opinion or idea or belief. In this talk, we explore a simple model of social contagion on a random network. We also look at the effect that network connectivity, edge distribution, and heterogeneity has on the diffusion of a contagion.

The talk slides are here.

Reading material:

• Mason A. Porter and James P. Gleeson, Dynamical systems on networks: a tutorial.

• Duncan J. Watts, A simple model of global cascades on random networks.


Complex Adaptive System Design (Part 9)

24 March, 2019

Here’s our latest paper for the Complex Adaptive System Composition and Design Environment project:

• John Baez, John Foley and Joe Moeller, Network models from Petri nets with catalysts.

Check it out! And please report typos, mistakes, or anything you have trouble understanding! I’m happy to answer questions here.

The idea

Petri nets are a widely studied formalism for describing collections of entities of different types, and how they turn into other entities. I’ve written a lot about them here. Network models are a formalism for designing and tasking networks of agents, which our team invented for this project. Here we combine these ideas! This is worthwhile because while both formalisms involve networks, they serve a different function, and are in some sense complementary.

A Petri net can be drawn as a bipartite directed graph with vertices of two kinds: places, drawn as circles, and transitions drawn as squares:

When we run a Petri net, we start by placing a finite number of dots called tokens in each place:

This is called a marking. Then we repeatedly change the marking using the transitions. For example, the above marking can change to this:

and then this:

Thus, the places represent different types of entity, and the transitions are ways that one collection of entities of specified types can turn into another such collection.

Network models serve a different function than Petri nets: they are a general tool for working with networks of many kinds. Mathematically a network model is a lax symmetric monoidal functor G \colon \mathsf{S}(C) \to \mathsf{Cat}, where \mathsf{S}(C) is the free strict symmetric monoidal category on a set C. Elements of C represent different kinds of ‘agents’. Unlike in a Petri net, we do not usually consider processes where these agents turn into other agents. Instead, we wish to study everything that can be done with a fixed collection of agents. Any object x \in \mathsf{S}(C) is of the form c_1 \otimes \cdots \otimes c_n for some c_i \in C; thus, it describes a collection of agents of various kinds. The functor G maps this object to a category G(x) that describes everything that can be done with this collection of agents.

In many examples considered so far, G(x) is a category whose morphisms are graphs of some sort whose nodes are agents of types c_1, \dots, c_n. Composing these morphisms corresponds to ‘overlaying’ graphs. Network models of this sort let us design networks where the nodes are agents and the edges are communication channels or shared commitments. In our first paper the operation of overlaying graphs was always commutative:

• John Baez, John Foley, Joe Moeller and Blake Pollard, Network models.

Subsequently Joe introduced a more general noncommutative overlay operation:

• Joe Moeller, Noncommutative network models.

This lets us design networks where each agent has a limit on how many communication channels or commitments it can handle; the noncommutativity lets us take a ‘first come, first served’ approach to resolving conflicting commitments.

Here we take a different tack: we instead take G(x) to be a category whose morphisms are processes that the given collection of agents, x, can carry out. Composition of morphisms corresponds to carrying out first one process and then another.

This idea meshes well with Petri net theory, because any Petri net P determines a symmetric monoidal category FP whose morphisms are processes that can be carried out using this Petri net. More precisely, the objects in FP are markings of P, and the morphisms are sequences of ways to change these markings using transitions, e.g.:

Given a Petri net, then, how do we construct a network model G \colon \mathsf{S}(C) \to \mathsf{Cat}, and in particular, what is the set C? In a network model the elements of C represent different kinds of agents. In the simplest scenario, these agents persist in time. Thus, it is natural to take C to be some set of ‘catalysts’. In chemistry, a reaction may require a catalyst to proceed, but it neither increases nor decrease the amount of this catalyst present. In everyday life, a door serves as a catalyst: it lets you walk though a wall, and it doesn’t get used up in the process!

For a Petri net, ‘catalysts’ are species that are neither increased nor decreased in number by any transition. For example, in the following Petri net, species a is a catalyst:

but neither b nor c is a catalyst. The transition \tau_1 requires one token of type a as input to proceed, but it also outputs one token of this type, so the total number of such tokens is unchanged. Similarly, the transition \tau_2 requires no tokens of type a as input to proceed, and it also outputs no tokens of this type, so the total number of such tokens is unchanged.

In Theorem 11 of our paper, we prove that given any Petri net P, and any subset C of the catalysts of P, there is a network model

G \colon \mathsf{S}(C) \to \mathsf{Cat}

An object x \in \mathsf{S}(C) says how many tokens of each catalyst are present; G(x) is then the subcategory of FP where the objects are markings that have this specified amount of each catalyst, and morphisms are processes going between these.

From the functor G \colon \mathsf{S}(C) \to \mathsf{Cat} we can construct a category \int G by ‘gluing together’ all the categories G(x) using the Grothendieck construction. Because G is symmetric monoidal we can use an enhanced version of this construction to make \int G into a symmetric monoidal category. We already did this in our first paper on network models, but by now the math has been better worked out here:

• Joe Moeller and Christina Vasilakopoulou, Monoidal Grothendieck construction.

The tensor product in \int G describes doing processes ‘in parallel’. The category \int G is similar to FP, but it is better suited to applications where agents each have their own ‘individuality’, because FP is actually a commutative monoidal category, where permuting agents has no effect at all, while \int G is not so degenerate. In Theorem 12 of our paper we make this precise by more concretely describing \int G as a symmetric monoidal category, and clarifying its relation to FP.

There are no morphisms between an object of G(x) and an object of G(x') when x \not\cong x', since no transitions can change the amount of catalysts present. The category FP is thus a ‘disjoint union’, or more technically a coproduct, of subcategories FP_i where i, an element of free commutative monoid on C, specifies the amount of each catalyst present.

The tensor product on FP has the property that tensoring an object in FP_i with one in FP_j gives an object in FP_{i+j}, and similarly for morphisms. However, in Theorem 14 we show that each subcategory FP_i also has its own tensor product, which describes doing one process after another while reusing catalysts.

This tensor product is a very cool thing. On the one hand it’s quite obvious: for example, if two people want to walk through a door, they can both do it, one at a time, because the door doesn’t get used up when someone walks through it. On the other hand, it’s mathematically interesting: it turns out to give a lot of examples of monoidal categories that can’t be made symmetric or even braided, even though the tensor product of objects is commutative! The proof boils down to this:



Here i represents the catalysts, and f and f' are two processes which we can carry out using these catalysts. We can do either one first, but we get different morphisms as a result.

The paper has lots of pictures like this—many involving jeeps and boats, which serve as catalysts to carry people first from a base to the shore and then from the shore to an island. I think these make it clear that the underlying ideas are quite commonsensical. But they need to be formalized to program them into a computer—and it’s nice that doing this brings in some classic themes in category theory!


Some posts in this series:

Part 1. CASCADE: the Complex Adaptive System Composition and Design Environment.

Part 2. Metron’s software for system design.

Part 3. Operads: the basic idea.

Part 4. Network operads: an easy example.

Part 5. Algebras of network operads: some easy examples.

Part 6. Network models.

Part 7. Step-by-step compositional design and tasking using commitment networks.

Part 8. Compositional tasking using category-valued network models.

Part 9 – Network models from Petri nets with catalysts.


Systems as Wiring Diagram Algebras

28 January, 2019

 

Check out the video of Christina Vasilakopoulou’s talk, the third in the Applied Category Theory Seminar here at U. C. Riverside! It was nicely edited by Paola Fernandez and uploaded by Joe Moeller.

Abstract. We will start by describing the monoidal category of labeled boxes and wiring diagrams and its induced operad. Various kinds of systems such as discrete and continuous dynamical systems have been expressed as algebras for that operad, namely lax monoidal functors into the category of categories. A major advantage of this approach is that systems can be composed to form a system of the same kind, completely determined by the specific way the composite systems are interconnected (‘wired’ together). We will then introduce a generalized system, called a machine, again as a wiring diagram algebra. On the one hand, this abstract concept is all-inclusive in the sense that discrete and continuous dynamical systems are sub-algebras; on the other hand, we can specify succinct categorical conditions for totality and/or determinism of systems that also adhere to the algebraic description.

Reading material:

• Patrick Schultz, David I. Spivak and Christina Vasilakopoulou, Dynamical systems and sheaves.

• David I. Spivak, The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug-and-play circuits.

• Dmitry Vagner, David I. Spivak and Eugene Lerman, Algebras of open dynamical systems on the operad of wiring diagrams.


The Mathematics of the 21st Century

13 January, 2019

 

Check out the video of my talk, the first in the Applied Category Theory Seminar here at U. C. Riverside. It was nicely edited by Paola Fernandez and uploaded by Joe Moeller.

Abstract. The global warming crisis is part of a bigger transformation in which humanity realizes that the Earth is a finite system and that our population, energy usage, and the like cannot continue to grow exponentially. If civilization survives this transformation, it will affect mathematics—and be affected by it—just as dramatically as the agricultural revolution or industrial revolution. We should get ready!

The slides are rather hard to see in the video, but you can read them here while you watch the talk. Click on links in green for more information!


Applied Category Theory Seminar

14 December, 2018

 

We’re going to have a seminar on applied category theory here at U. C. Riverside! My students have been thinking hard about category theory for a few years, but they’ve decided it’s time to get deeper into applications. Christian Williams, in particular, seems to have caught my zeal for trying to develop new math to help save the planet.

We’ll try to videotape the talks to make it easier for you to follow along. I’ll also start discussions here and/or on the Azimuth Forum. It’ll work best if you read the papers we’re talking about and then join these discussions. Ask questions, and answer any questions you can!

Here’s how the schedule of talks is shaping up so far. The talks are on Tuesdays 3:34–5:00 pm in Room 268 of Skye Hall, the mathematics building at U. C. Riverside.

January 8, 2019: John Baez
Mathematics in the 21st century

Abstract. The global warming crisis is part of a bigger transformation in which humanity realizes that the Earth is a finite system and that our population, energy usage, and the like cannot continue to grow exponentially. If civilization survives this transformation, it will affect mathematics – and be affected by it – just as dramatically as the agricultural revolution or industrial revolution. We should get ready!

Talk slides: Mathematics in the 21st century.

Also try these slides and videos from related talks:

The mathematics of planet Earth.

Props in network theory.

January 15, 2019: Jonathan Lorand
Classification problems in symplectic linear algebra

Abstract. In this talk we will look at various examples of classification problems in symplectic linear algebra: conjugacy classes in the symplectic group and its Lie algebra, linear lagrangian relations up to conjugation, tuples of (co)isotropic subspaces. I will explain how many such problems can be encoded using the theory of symplectic poset representations, and will discuss some general results of this theory. Finally, I will recast this discussion from a broader category-theoretic perspective.

Talk slides: Problems in symplectic linear algebra.

Reading material:

• Jonathan Lorand, Classifying linear canonical relations.

• Jonathan Lorand and Alan Weinstein, Decomposition of (co)isotropic relations.

January 22, 2019: Christina Vasilakopoulou
Systems as wiring diagram algebras

Abstract. We will start by describing the monoidal category of labeled boxes and wiring diagrams and its induced operad. Various kinds of systems such as discrete and continuous dynamical systems have been expressed as algebras for that operad, namely lax monoidal functors into the category of categories. A major advantage of this approach is that systems can be composed to form a system of the same kind, completely determined by the specific way the composite systems are interconnected (‘wired’ together). We will then introduce a generalized system, called a machine, again as a wiring diagram algebra. On the one hand, this abstract concept is all-inclusive in the sense that discrete and continuous dynamical systems are sub-algebras; on the other hand, we can specify succinct categorical conditions for totality and/or determinism of systems that also adhere to the algebraic description.

Christina Vasilakopoulou’s talk was based on this paper:

• Patrick Schultz, David I. Spivak and Christina Vasilakopoulou, Dynamical systems and sheaves.

but she focused more on the algebraic description (and conditions for deterministic/total systems) rather than the sheaf theoretic aspect of the input types. This work builds on earlier papers such as these:

• David I. Spivak, The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug-and-play circuits.

• Dmitry Vagner, David I. Spivak and Eugene Lerman, Algebras of open dynamical systems on the operad of wiring diagrams.

January 29, 2019: Daniel Cicala
Social contagion modeled on random networks

Abstract. A social contagion may manifest as a cultural trend, a spreading opinion or idea or belief. In this talk, we explore a simple model of social contagion on a random network. We also look at the effect that network connectivity, edge distribution, and heterogeneity has on the diffusion of a contagion.

Talk slides: Social contagion modeled on random networks.

Reading material:

• Mason A. Porter and James P. Gleeson, Dynamical systems on networks: a tutorial.

• Duncan J. Watts, A simple model of global cascades on random networks.

February 5, 2019: Jade Master
Backprop as functor: a compositional perspective on supervised learning

Abstract. Fong, Spivak and Tuyéras have found a categorical framework in which gradient descent algorithms can be constructed in a compositional way. To explain this, we first give a brief introduction to backprogation and gradient descent. We then describe their monoidal category Learn, where the morphisms are given by abstract learning algorithms. Finally, we show how gradient descent can be realized as a monoidal functor from Para, the category of Euclidean spaces with differentiable parameterized functions between them, to Learn.

Reading material:

• Brendan Fong, David I. Spivak and Rémy Tuyéras, Backprop as functor: a compositional perspective on supervised learning.

February 12, 2019: Christian Williams
The pi calculus: towards global computing

Abstract. Historically, code represents a sequence of instructions for a single machine. Each computer is its own world, and only interacts with others by sending and receiving data through external ports. As society becomes more interconnected, this paradigm becomes more inadequate – these virtually isolated nodes tend to form networks of great bottleneck and opacity. Communication is a fundamental and integral part of computing, and needs to be incorporated in the theory of computation.

To describe systems of interacting agents with dynamic interconnection, in 1980 Robin Milner invented the pi calculus: a formal language in which a term represents an open, evolving system of processes (or agents) which communicate over names (or channels). Because a computer is itself such a system, the pi calculus can be seen as a generalization of traditional computing languages; there is an embedding of lambda into pi – but there is an important change in focus: programming is less like controlling a machine and more like designing an ecosystem of autonomous organisms.

We review the basics of the pi calculus, and explore a variety of examples which demonstrate this new approach to programming. We will discuss some of the history of these ideas, called “process algebra”, and see exciting modern applications in blockchain and biology.

“… as we seriously address the problem of modelling mobile communicating systems we get a sense of completing a model which was previously incomplete; for we can now begin to describe what goes on outside a computer in the same terms as what goes on inside – i.e. in terms of interaction. Turning this observation inside-out, we may say that we inhabit a global computer, an informatic world which demands to be understood just as fundamentally as physicists understand the material world.” — Robin Milner

Talk slides: The pi calculus: towards global computing.

Reading material:

• Robin Milner, The polyadic pi calculus: a tutorial.

• Robin Milner, Communicating and Mobile Systems.

• Joachim Parrow, An introduction to the pi calculus.

February 19, 2019: Kenny Courser
Category theory for genetics

Abstract. Rémy Tuyéras has developed a categorical framework aimed at handling various commonly studied subjects from the theory of genetics. Some of these include alignment methods, CRISPR, homologous recombination, haplotypes, and genetic linkage. In this talk, I will introduce the foundations on which this framework is built and give a few examples related to DNA and RNA sequencing which are able to be described in this environment.

Reading material:

• Rémy Tuyéras, Category theory for genetics.


ACT 2019 – First Announcement

2 October, 2018

 

animation by Marius Buliga

I’m helping organize ACT 2019, an applied category theory conference and school at Oxford, July 15-26, 2019.

If you’re a grad student or postdoc interested in this subject, you should apply for the ‘school’ before January 30th. Later people can submit papers for the conference:

Dear all,

As part of a new growing community in Applied Category Theory, now with a dedicated journal Compositionality, a traveling workshop series SYCO, a forthcoming Cambridge U. Press book series Reasoning with Categories, and several one-off events including at NIST, we launch an annual conference+school series named Applied Category Theory, the coming one being at Oxford, July 15-19 for the conference, and July 22-26 for the school. The dates are chosen such that CT 2019 (Edinburgh) and the ACT 2019 conference (Oxford) will be back-to-back, for those wishing to participate in both.

There already was a successful invitation-only pilot, ACT 2018, last year at the Lorentz Centre in Leiden, also in the format of school+workshop.

For the conference, for those who are familiar with the successful QPL conference series, we will follow a very similar format for the ACT conference. This means that we will accept both new papers which then will be published in a proceedings volume (most likely a Compositionality special Proceedings issue), as well as shorter abstracts of papers published elsewhere. There will be a thorough selection process, as typical in computer science conferences. The idea is that all the best work in applied category theory will be presented at the conference, and that acceptance is something that means something, just like in CS conferences. This is particularly important for young people as it will help them with their careers.

Expect a call for submissions soon, and start preparing your papers now!

The school in ACT 2018 was unique in that small groups of students worked closely with an experienced researcher (these were John Baez, Aleks Kissinger, Martha Lewis and Pawel Sobociński), and each group ended up producing a paper. We will continue with this format or a closely related one, with Jules Hedges and Daniel Cicala as organisers this year. As there were 80 applications last year for 16 slots, we may want to try to find a way to involve more students.

We are fortunate to have a number of private sector companies closely associated in some way or another, who will also participate, with Cambridge Quantum Computing Inc. and StateBox having already made major financial/logistic contributions.

On behalf of the ACT Steering Committee,

John Baez, Bob Coecke, David Spivak, Christina Vasilakopoulou