COVID inspires to solve a 30-year-old problem in computer science

During the corona epidemic many of us became amateur mathematicians. How quickly would the number of hospitalized patients rise, and when would herd immunity be achieved? Professional mathematicians were challenged as well, and a researcher at University of Copenhagen became inspired to solve a 30-year-old problem in computer science. The breakthrough has just been published by the prestigious Journal of the ACM (Association for Computing Machinery).

Like many others, I was out to calculate how the epidemic would develop. I wanted to investigate certain ideas from theoretical computer science in this context. However, I realized that the lack of solution to the old problem was a showstopper." 

Joachim Kock, Associate Professor at the Department of Mathematics, University of Copenhagen

His solution to the problem can be of use in epidemiology and computer science, and potentially in other fields as well. A common feature for these fields is the presence of systems where the various components exhibit mutual influence. For instance, when a healthy person meets a person infected with COVID, the result can be two people infected.

Smart method invented by German teenager

To understand the breakthrough, one needs to know that such complex systems can be described mathematically through so-called Petri nets. The method was invented in 1939 by German Carl Adam Petri (by the way at the age of only 13) for chemistry applications. Just like a healthy person meeting a person infected with COVID can trigger a change, the same may happen when two chemical substances mix and react.

In a Petri net the various components are drawn as circles while events such as a chemical reaction or an infection are drawn as squares. Next, circles and squares are connected by arrows which show the interdependencies in the system.

A simple version of a Petri net for COVID infection. The starting point is a non-infected person. "S" denotes "susceptible". Contact with an infected person ("I") is an event which leads to two persons being infected. Later another event will happen, removing a person from the group of infected. Here, "R" denotes "recovered" which in this context could be either cured or dead. Either outcome would remove the person from the infected group.

Computer scientists regarded the problem as unsolvable

In chemistry, Petri nets are applied for calculating how the concentrations of various chemical substances in a mixture will evolve. This manner of thinking has influenced the use of Petri nets in other fields such as epidemiology: we are starting out with a high "concentration" of un-infected people, whereafter the "concentration" of infected starts to rise. In computer science, the use of Petri nets is somewhat different: the focus is on individuals rather than concentrations, and the development happens in steps rather than continuously.

What Joachim Kock had in mind was to apply the more individual-oriented Petri nets from computer science for COVID calculations. This was when he encountered the old problem:

"Basically, the processes in a Petri net can be described through two separate approaches. The first approach regards a process as a series of events, while the second approach sees the net as a graphical expression of the interdependencies between components and events," says Joachim Kock, adding:

"The serial approach is well suited for performing calculations. However, it has a downside since it describes causalities less accurately than the graphical approach. Further, the serial approach tends to fall short when dealing with events that take place simultaneously."

"The problem was that nobody had been able to unify the two approaches. The computer scientists had more or less resigned, regarding the problem as unsolvable. This was because no-one had realized that you need to go all the way back and revise the very definition of a Petri net," says Joachim Kock.

Small modification with large impact

The Danish mathematician realized that a minor modification to the definition of a Petri net would enable a solution to the problem:

"By allowing parallel arrows rather than just counting them and writing a number, additional information is made available. Things work out and the two approaches can be unified."

The exact mathematical reason why this additional information matters is complex, but can be illustrated by an analogy:

"Assigning numbers to objects has helped humanity greatly. For instance, it is highly practical that I can arrange the right number of chairs in advance for a dinner party instead of having to experiment with different combinations of chairs and guests after they have arrived. However, the number of chairs and guests does not reveal who will be sitting where. Some information is lost when we consider numbers instead of the real objects."

Similarly, information is lost when the individual arrows of the Petri net are replaced by a number.

"It takes a bit more effort to treat the parallel arrows individually, but one is amply rewarded as it becomes possible to combine the two approaches so that the advantages of both can be obtained simultaneously."

The circle to COVID has been closed

The solution helps our mathematical understanding of how to describe complex systems with many interdependencies, but will not have much practical effect on the daily work of computer scientists using Petri nets, according to Joachim Kock:

"This is because the necessary modifications are mostly back-compatible and can be applied without need for revision of the entire Petri net theory."

"Somewhat surprisingly, some epidemiologists have started using the revised Petri nets. So, one might say the circle has been closed!"

Joachim Kock does see a further point to the story:

"I wasn't out to find a solution to the old problem in computer science at all. I just wanted to do COVID calculations. This was a bit like looking for your pen but realizing that you must find your glasses first. So, I would like to take the opportunity to advocate the importance of research which does not have a predefined goal. Sometimes research driven by curiosity will lead to breakthroughs."