On Classes of Distributed Petri Nets

Schicke-Uffmann, Jens-Wolfhard

doi:10.24355/dbbs.084-201809061234-0

Published

On Classes of Distributed Petri Nets

English
German

This thesis considers -- on a fundamental, and theoretical level -- the question which behaviours respectively algorithms can be realized in a distributed system. It employs Petri nets and various behavioural equivalences to model such systems. Based upon those, it identifies an M-shaped structure as the smallest undistributable Petri net and proves that this identification is stable across a wide swath of the linear-time branching-time spectrum of behavioural equivalences, collected by Glabbeek. It also gives a constructive proof that all Petri nets not containing such a structure are fully distributable. It employs this construction in a prototypical compiler from Petri nets to distributed (via TCP/IP) Linux binaries which was used to test (and fix) said construction. Finally, multiple ways to evade the undistributability theorem's assumptions are discussed, to enable the distributed implementation of necessary behaviours nonetheless.

Die Arbeit untersucht -- auf theoretischer und damit fundamentaler Basis -- die Frage welche Verhaltensweisen beziehungsweise Algorithmen durch ein verteiltes System realisiert werden können. Solche Systeme werden dazu durch Petrinetze und verschiedene Verhaltensäquivalenzen modelliert. Innerhalb dieses Modells wird eine M-förmige Struktur als das kleinste unverteilbare Petrinetz identifiziert und gezeigt, dass diese Eigenschaft über einen großen Bereich des durch Glabbeek beschriebenen Linear-Time Branching-Time Spektrums der Verhaltensäquivalenzen stabil bleibt. Die Arbeit enthält weiter einen konstruktiven Beweis, dass alle Petrinetze ohne diese Struktur vollständig verteilbar sind. Die enthaltene Konstruktion wird dann in einem prototypischen Compiler von Petrinetzen nach verteilten (via TCP/IP) Linux-Binaries verwendet, um die Konstruktion zu testen (und zu korrigieren). Schließlich werden verschiedene Wege diskutiert, wie sich die Vorbedingungen des Unverteilbarkeitstheorems umgehen lassen, um notwendige Verhaltensweisen dennoch verteilt implementieren zu können.