Skip to content

Carl Adam Petri and Petri Nets

Abstract

Carl Adam Petri (1926–2010) submitted a dissertation to the Technische Hochschule Darmstadt in 1961 arguing that a theory of computing should start from components that act locally and asynchronously, without a global clock or a global state. The notation he developed for this, places, transitions, and tokens, became known as Petri nets. A Bell Labs simulation team drew one in 1964, American projects took them up in the late 1960s, and their token rules now sit under UML activity diagrams and most business-process notations. Petri spent the rest of his career, mostly at the GMD near Bonn, on a wider theory of nets that the field largely left unread.

Carl Adam Petri
Carl Adam Petri. Image: Michael Krapp, derivative work AwOc, CC BY-SA 3.0, via Wikimedia Commons.

Leipzig, the War, and England

Petri was born in Leipzig on 12 July 1926. His father held a doctorate in mathematics and had met Minkowski and Hilbert. For his twelfth birthday the boy received two thick chemistry textbooks from a bankrupt bookseller’s estate and worked through both; his father arranged a special permit for the Leipzig central library, where he read Einstein and Heisenberg. In August 1939, aged 13, he devised a graphical notation to describe chemical reactions. Petri later dated the idea of his nets to that summer.

In 1941 his father told him about Konrad Zuse’s calculating machines, and Petri started building an analog computer of his own. He took his Abitur at the Thomasschule in 1944 and was drafted at once. As a young anti-aircraft auxiliary he had watched officers estimate the height, distance, and speed of approaching aircraft by eye and ear. Who was responsible for the errors that such estimates inevitably produced was a question that stayed with him. He became a British prisoner of war and remained in England until 1949, where he solved surveying problems such as laying out concentric ellipses on rolling ground.

A Dissertation About Clocks

Petri studied mathematics at the Technische Hochschule Hannover from 1950 and followed his teacher Heinz Unger to the University of Bonn, where he worked from 1959. He submitted Kommunikation mit Automaten (Communication with Automata) to the science faculty of TH Darmstadt in July 1961 and defended it in June 1962. It was printed the same year as number 2 in the series of the Rheinisch-Westfälisches Institut für Instrumentelle Mathematik in Bonn. Alwin Walther, Darmstadt’s computing pioneer, saw to it that it was named the faculty’s best dissertation of 1961/62.

The thesis starts from a practical problem. For a general recursive function, nobody can say in advance how much intermediate storage a computation will need. A machine that runs out has to be enlarged and restarted. Petri asked whether a machine could instead grow while it runs. With a central clock it cannot: every extension lengthens the wires, the clock has to slow down to cover the longer signal paths, and the fan-out of the clock generator, and with it its power draw, grows without limit.

His solution was to attach each new component only to the one added before it. That works if every component acts on its own and the whole system runs asynchronously. As a feasibility proof he designed an asynchronous pushdown store built from modules that each hold one data element and talk only to their two neighbours. Two such stores can simulate a Turing machine, so the design is computationally universal. Petri presented it at the first IFIP congress in Munich in 1962 (see IFIP). His conclusion was that a theory of information processing had to be built on asynchronous, locally bounded operations, and that sequential models were the wrong foundation.

Places, Transitions, and Tokens

The dissertation used several notations. The one that survived uses two kinds of nodes. Places, drawn as circles, stand for local conditions; transitions, drawn as bars or boxes, stand for local actions. Arrows connect places to transitions and transitions to places. Tokens sit in places and mark which conditions currently hold. A transition may fire when every one of its input places holds a token; firing removes those tokens and puts new ones into its output places. Only the places next to the transition change, and nothing in the rule refers to the rest of the system. The form now taught in textbooks appeared in Petri’s talk at the third colloquium on automata theory in Hannover, printed in 1967.

Info

A standard classroom example is mutual exclusion. Two processes each cycle between “working” and “printing”, and a single place labelled “printer free” holds one token. Each process’s “start printing” transition needs that token, and its “stop printing” transition puts it back. Because there is only one token, the net makes it visible, and provable from the structure alone, that the two processes can never print at the same time.

The deeper point for Petri was what a run of such a system looks like. He did not want events lined up on an idealized global time axis. A run was a partial order induced by cause and effect: if neither of two events depends on the outcome of the other, they are unordered, and Petri called that relation concurrency. Concurrency in this sense is not transitive, unlike “happening at the same time”. Petri took the picture from relativity, where every event has a cone of events that can influence it and a cone it can influence. Brauer and Reisig note that the same causal-order idea later turned up independently in the work of Leslie Lamport and others.

Bell Labs and the Americans

The first practical use came before most theorists had heard of the thesis. At the end of 1964 Bell Labs was building ESS No. 1, the first commercial stored-program telephone switch. The simulation team, run by Erna Hoover, worked from a large diagram that Hoover called a Petri net, with some of its complicated nodes expanded into nets of their own. Tom DeMarco, a member of that team, recalled in Software Pioneers (2002) that it was the document they used most, and quoted a colleague, Jut Kodner: “the diagram was a better spec than the spec.”

An English translation of the dissertation appeared in 1966 as a technical report for the US Air Force’s Rome Air Development Center, produced by Applied Data Research in Princeton, where Anatol Holt led an “Information System Theory Project”. Holt and Commoner’s report Events and Conditions (April 1970) reworked Petri’s ideas for American readers, and MIT’s Project MAC took nets up at the end of the 1960s. One MIT line of work studied nets through the formal languages their firing sequences generate. Petri disliked it: reducing a run to a sequence of firings threw away exactly the distinction between concurrent and causally ordered events that he considered fundamental.

The GMD Years

After his doctorate Petri set up and ran the computing centre of the University of Bonn from 1963 to 1968. In 1968 he became head of the Institut für Informationssystemforschung at the newly founded Gesellschaft für Mathematik und Datenverarbeitung (GMD) in Birlinghoven near Bonn, an institute now part of the Fraunhofer Society. He turned down a full professorship at the University of Dortmund in 1973 and ran the institute until he retired in 1991. The University of Hamburg made him an honorary professor in 1988.

Recognition built slowly and then arrived from several directions. The first Advanced Course on Petri Nets, held in Hamburg in 1979 and edited by Wilfried Brauer, collected the theoretical results and case studies of the 1970s, including linear-algebra methods for computing place and transition invariants. An annual International Conference on Applications and Theory of Petri Nets has run since 1980. In the 1980s nets gained individual, “coloured” tokens of different kinds, which made them practical for larger engineering models. Robin Milner used his 1991 Turing Award lecture to say: “Much of what I have been saying was already well understood in the sixties by Carl Adam Petri, who pioneered the scientific modeling of discrete concurrent systems.”

The engineering world honoured him too. In 1997 Petri received the Werner von Siemens Ring, the second computer scientist after Zuse to do so; the laudation credited nets with giving engineers their first technique for both describing and analysing discretely controlled systems. The GI’s Konrad Zuse Medal followed in 1993 and the IEEE Computer Pioneer Award in 2008, “for establishing Petri net theory in 1962.” Petri died in Siegburg on 2 July 2010, aged 83.

From Theory of Nets to Workflow Diagrams

The place where most people meet Petri’s nets today is a process diagram. The activity diagrams of UML 2 build on Petri-net components, with tokens flowing along their edges. Wil van der Aalst’s paper “The Application of Petri Nets to Workflow Management” (1998) defined workflow nets, a class of Petri nets with one start and one end place, and gave a soundness criterion for business processes. BPMN 2.0, the Object Management Group’s standard notation for business processes, explains its execution rules with tokens as well, calling them “a theoretical concept” used to define behaviour. In 2015 van der Aalst summed up the situation: mainstream process-modelling languages and workflow systems use token semantics borrowed from Petri nets, and BPM analysis tools use nets as their internal representation, mostly without their users knowing it.

Dead End: The General Theory

What industry adopted was the diagram and its firing rule. What Petri himself worked on for forty years was something larger, and most of it stayed with him and his group.

His dissertation already demanded three things of a theory of computing. It should obey physics: no global states, and an ordering of events by cause and effect instead of a fictitious clock. It should rest on conservation laws, the way chemistry rests on balanced reaction equations, which led him to reversible actions (an assignment x := x + 1 can be undone, x := 1 cannot). And it should describe the pragmatics of how people use computers to communicate with each other, the second meaning of “communication with automata”. Over the following decades he developed these into a general net theory with its own axioms, concepts of measurement inspired by his wartime question about estimation errors, and proposals for a notion of information that is conserved during processing.

Few took these up. The applied side wanted modelling tools, which it got. The theoretical side moved through the 1980s towards process algebras, such as Milner’s work and later the π-calculus, and towards temporal logic in the line begun by Amir Pnueli (see Formal Methods and Model Checking). Partial-order reduction in model checking is the clearest place where Petri’s partially ordered runs paid off, but it reached him as a technique, not as a foundation. In an invited talk at the Petri net conference in Miami in June 2005 he praised the range of applications and asked for something else: no more classes of nets or cleverer analysis algorithms, but a return to the long-term aims of 1962. Brauer and Reisig, writing the next year, put the reason the request went unanswered plainly: in a field run on short projects, “Petri rarely would have got a chance.”

📚 Sources