COVID calculations lead to unexpected solution to long-standing problem in theoretical computer science

At the beginning of the COVID-19 pandemic, Joachim Kock, mathematician at the Universitat Autònoma de Barcelona (UAB), began to experiment with epidemiological models. He did not improve upon the predictions, but unexpectedly he made a mathematical discovery that led to the solution of an old problem in theoretical computer science, open since the 1980s, on Petri nets. The result has just been published in the prestigious Journal of the ACM.

One of the simplest and most used mathematical models for the spread of infectious diseases is the so-called SIR model. The model considers the population assigned to three compartments: susceptible (S) (that is, healthy individuals), infectious (I), and recovered (R). It further stipulates two possible transitions between these compartments: one occurs when a susceptible individual encounters an infectious, resulting in two infectious individuals; the other transition consists in an infectious individual recovering.

This model can be analysed mathematically via the tool called Petri nets, a class of networks with compartments and transitions, linked up with weighted arrows reflecting the relations between compartments and transitions (see the figure). From a given Petri net, equipped with constants indicating the transition rates of each transition (these constants must be determined experimentally), the model prescribes the evolution of the population compartments, and hence the disease.

When at the beginning of the pandemic UAB researcher Joachim Kock began to model COVID-19 using Petri nets, he wanted to experiment with the idea of considering actual individuals rather than just compartments, an idea inspired by the use of Petri nets in theoretical computer science.

There Petri nets are considered equipped with a certain number of tokens in each compartment, which move according to the transitions, with the rule that a transition can take place only if there are enough tokens in the input compartments: these tokens are then consumed, and as a result tokens will be produced in the output compartments. The most important use of Petri nets in computer science is as a model for concurrent computation. In that context there is an old problem, open since the 1980s, namely that there exist two different approaches to reasoning mathematically about Petri nets as a model of concurrency, — two semantics, as it is called — which could not be reconciled: one is an algebraic semantics, the other is a geometric semantics, each with its advantages and drawbacks.

“COVID-19 simluation with computer-science-style Petri nets, was not a success from the viewpoint of epidemiology,” Kock explains. “The formalism actually does not allow to trace individuals as tokens. There is an obstruction, and it turned out to be the same obstruction that prevented the reconciliation of the geometric and algebraic semantics, the old problem!”

In order to find a solution, the UAB researcher embarked on a general revision of Petri net theory. He discovered that it was necessary to adjust the very definition of Petri net, so as to allow parallel arrows instead of weights. In other words, pass from a number (the weight of an arrow) to a set of arrows with that number of elements. “In homotopy theory, which is one of my fields of research, this kind of consideration is quite common,” Kock explains. “In this case, the introduction of these sets of arrows leads to the appearance of symmetries which are not visible in the conventional Petri nets, where there is only a number, not a set.” What was missing in the conventional Petri nets was precisely access to this information of symmetries of Petri nets, provided in Kock’s new notion. “With a little bit of homotopy theory and category theory, I could prove that the new version of Petri nets allows a reconciliation of the two semantics, the algebraic and the geometric.”

The new definition proposed by Kock has already been used by other researchers (Evan Patterson and his group in Berkeley, USA) to develop Petri-net based software for epidemiological modelling, and in particular for COVID research. “In this way the circle has been closed.

Abstract mathematics allows transfer of knowledge from one field of science to another, in this case quite unexpectedly. I was looking for one thing but ended up finding another. Sometimes it is fruitful to experiment with ideas without knowing in advance where they may lead,” Kock concludes.