Algebraic Structures for the Analysis of Distributability of Elementary Systems and their Processes

This work studies systems, and the processes they execute, in the way they can be distributed. To this aim, the central notion is that when a system is distributed, a remote observation requires an exchange of information from the different locations of the system. This approach is characterised by the fact that handshaking is the basic mode of interaction. The chosen formalisms are taken in the framework Petri net theory. Elemen- tary net systems, and condition/event net systems provide specifications for the systems. Causal nets and partially ordered sets allow for modelling processes. With these last formalisations, the state of the art provides a notion of subpro- cesses that can be structured so as to carry information on how a process can be distributed. This structure is formalised as an orthomodular lattice. This work shows that the minimal non trivial elements of this lattice, the minimal subprocesses, can be ordered so as to provide an abstraction of the process. The nature of this notion of subprocess permits to show that this abstraction depicts the localities of the process, parts of the process which can run independently from each other. The behaviour of elementary, and condition/event net systems, is modelled with labelled transition systems. This work adheres to an interpretation of the set of elementary regions, as the one of locally observable properties of the sys- tem, motivated by elementary net synthesis. According to this interpretation, elementary regions represent a suitable specification of the available infrastruc- ture on which to distribute a system. The state of the art shows that the set of regions of an elementary, or condition/event system, forms an orthomodular poset, and a way to retrieve a canonical labelled transition system such that all regions of the orthomodular poset are also regions of it. The question of whether this canonical transition system has more regions than the specified ones is an open problem. The canonical transition system is the largest one can obtain from an orthomodular poset, in the sense that systems complying with the specification, can be found as subsystems of it. However, not all its subsystems display the same regional structure. This work presents a sufficient condition for this to happen. This is achieved by providing a structure to the set of events, or labels, of the canonical system, which reflects concurrency. An orthomodular poset is called stable when it is isomorphic to the set of regions of its canonical transition system. The state of the art shows that when the first poset is of a given class, it embeds in the second. It is conjectured that all posets that arise as the set of elementary regions of an elementary system, regional posets, are stable. This work provides a condition necessary for an orthomodular poset to be regional, and shows that when it holds, the embedding is strong. Not every embedding is strong, but all isomorphisms are, in particular, strong embeddings. This result implies that the embedding maps minimal regions to minimal regions.

In questa tesi studio in che modi si possono distribuire i sistemi e i processi che quei sistemi eseguono. La nozione centrale per raggiungere l'obiettivo è che, quando un sistema è distribuito, una sua osservazione "da lontano" richiede uno scambio d'informazioni con le diverse parti del sistema. Questo approccio si caratterizza per il fatto che la "sincronizzazione" (o "handshaking") è il modo fondamentale di interazione. I formalismi impiegati sono presi dalla teoria delle reti di Petri. I sistemi elementari e i sistemi di condizioni ed eventi in quella teoria costituiscono le specificazioni di sistemi. Le reti causali e gli insiemi parzialmente ordinati permettono di modellare processi. In questi modelli, lo stato dell'arte offre una nozione di sottoprocesso, cui si può associare una struttura che porta l'informazione su come distribuire il processo. Formalmente, questa struttura è un reticolo ortomodulare. Nella tesi mostro che gli elementi minimali non banali di quel reticolo (sottoprocessi minimali) possono essere ordinati in modo da formare un'astrazione del processo dato. La natura di questa nozione di sottoprocesso consente di mostrare che l'astrazione rappresenta le componenti del processo, cioè le parti che possono operare indipendentemente. Il comportamento dei sistemi elementari e dei sistemi di condizioni e eventi è modellato per mezzo di sistemi di transizioni etichettate. Nella tesi si applica un'interpretazione delle regioni elementari come proprietà localmente osservabili del sistema, motivata dalla sintesi di reti elementari. Secondo questa interpretazione, le regioni elementari offrono una specificazione adeguata dell'infrastruttura su cui si può distribuire un sistema. Era già noto che l'insieme delle regioni di un sistema elementare o di condizioni ed eventi forma un insieme ortomodulare, da cui si può ricavare un sistema di transizioni etichettate canonico, che contiene tutte le regioni dell'insieme ortomodulare dato. Stabilire se il sistema canonico ha più regioni di quelle specificate è un problema aperto. Il sistema canonico è il più "grande" che si può ottenere dall'insieme ortomodulare, nel senso che ogni altro sistema conforme alla specificazione è un suo sottosistema. D'altra parte, non tutti i sottosistemi hanno la stessa struttura regionale. Definisco una condizione sufficiente per avere l'isomorfismo. Il risultato si ottiene dotando di un'opportuna struttura l'insieme degli eventi, o delle etichette, del sistema canonico, così da riflettere la concorrenza. Un insieme ortomodulare si dice stabile quando è isomorfo all'insieme delle regioni del sistema di transizioni canonico derivato. Erano già note condizioni sotto le quali il primo insieme si immerge nel secondo. Si congettura che tutti gli insiemi parzialmente ordinati ottenuti come insiemi di regioni di sistemi elementari (insiemi regionali) sono stabili. Nella tesi si dà una nuova condizione necessaria perché un insieme ortomodulare sia regionale, e si mostra che in quel caso l'immersione è forte. Non tutte le immersioni sono forti, ma tutti gli isomorfismi sono immersioni forti. Dal risultato segue che l'immersione mappa regioni minimali su regioni minimali.