E disszertációban a reakciórendszerek (Reaction Systems) nevű számítási modell reverzibilitását vizsgáló kutatásunkat mutatjuk be. Motivációnkat az jelentette, hogy különböző reverzibilitási paradigmákat próbálhassunk ki egyazon számítási modellen belül. Ennek megfelelően, munkánk a visszalépéses (backtracking) reverzibilitás megvalósításától egy olyan variánsig terjed, mely az okozati konzisztens (causal consistent) reverzibilitás implementálására is alkalmas.

A visszalépéses reverzibilitási paradigma olyan számítási módszerek esetén ideális, melyek a számításokat lépésről lépésre, azaz szekvenciálisan végzik. Mivel a reakciórendszerek is szekvenciális végrehajtással rendelkeznek, ezért természetesen adódott, hogy elsőként a kontrollálatlan visszalépéses paradigmát valósítjuk meg benne. Definíciónk szerint egy reakciórendszer reverzibilis, amennyiben annak minden interaktív folyamata reverzibilis. E definícióra építve meghatároztuk a reverzibilitás szükséges és elégséges feltételeit, megfelelő követelményeket támasztva a reakciókkal és a háttérhalmazzal szemben. Később a reverzibilis reakciórendszer definíciónkat kiegészítjük egy külső kontroll mechanizmussal is (external control). Azaz, egy olyan modellt készítettünk, melyben a számítás iránya a környezettől kapott bemenettől függ

A reverzibilis modell definiálása után, annak intuitív számítási erejét tekintettük, segítségül hívva az átmeneti gráfokat (transition graph). Elsőként az eredeti definíció szerint reverzibilis reakciórendszereket tekintettük, melyek igen korlátozottak: egy ilyen rendszer átmeneti gráfja vagy egyetlen csúcs, vagy pedig egy olyan irányított fa, melyben minden él a gyökérrel ellentétes irányba mutat. Ezt követően az úgynevezett visszatekintő reverzibilis rendszerekkel dolgoztunk (reversible with lookbehind). E változtatás eredményeként egy olyan modell állt elő, melynek viselkedése lényegében megegyezik a véges állapotátmeneti rendszerekével. Azaz, a reverzibilis véges állapotátmeneti rendszerek állapotátmeneti gráfjai megfelelnek a visszatekintő reverzibilis reakciórendszerek átmeneti gráfjainak. És fordítva, bármely visszatekintő reverzibilis reakciórendszer gráfjából felírható egy reverzibilis véges állapot-átmeneti rendszer állapot-átmeneti gráfja.

A kutatómunkánk elsődleges célja és motivációja a reverzibilitás különböző paradigmáinak vizsgálata volt. E motiváció mentén, a visszalépéses reverzibilitás után a figyelmünket egy másik paradigmára, az okozati konzisztenciára (causal consistency) fordítottuk.

Visszatekintve azonban a reakciórendszer eredeti definíciójára, az egy szekvenciális modellt ír le, mely nem tartalmaz konkurens viselkedést, értelmetlenné téve ezzel az okozati konzisztencia alkalmazását. Ahhoz, hogy a szekvenciális végrehajtáson továbbléphessünk, egy megfelelő variánsra van szükségünk. Egy ilyen variáns a közvetlenül kommunikáló reakciórendszerek (Communicating Reaction Systems with Direct Communication, cdcR systems). Ezen megfelelő módosításokat végrehajtva, bemutattunk egy általunk felírt közvetlenül kommunikáló reakciórendszer-variánst, melyet közvetlenül kommunikáló elosztott reakciórendszernek (Distributed Communicating Reaction Systems, d-cdcR systems) neveztünk el. E változat bevezeti a blokkolt (blocking) számításokat és az aktív komponenseket, megszüntetve ezzel a globális szinkronizációt. Mivel e módon lehetségessé váltak a konkurens számítások, így erre a modellre már felírhattuk az okozati konzisztens reverzibilitást, felhasználva Lanese, Phillips és Ulidowski kapcsolódó keretrendszerét.

Implementációnk két rétegből áll. Egyfelől, megköveteltük, hogy minden egyes komponens lokálisan reverzibilis legyen, megfelelve a korábban támasztott követelményeknek. Másfelől, a teljes d-cdcR rendszert tekintve, az egyes komponensek között zajló kommunikációt a komponensekhez csatolt vermekben tároltuk.

In this dissertation, we present our research about Reversible Reaction Systems. With the initial motivation of exploring different paradigms of reversibility within the same computational model, we started by implementing backtracking and finished with a variant that hosts causal-consistent reversibility.

Backtracking is a paradigm of reversibility best suited for sequential models of computation. This paradigm builds on the notion of ``last performed action'' and involves recursive undo until reaching the desired state. Since the original definition of Reaction Systems describes a model that operates sequentially on the level of interactive processes (with parallelism only in terms of applying reactions), we implemented uncontrolled backtracking reversibility for Reaction Systems. We stated the necessary and sufficient conditions for a reaction system to be reversible, posing restrictions on the reactions and creating a separate, non-disjoint input and product alphabet. Then, we extended our previous definition of Reversible Reaction Systems with external control. We constructed simulators of reversible systems that change the direction of computation based on the input from the environment.

After defining a reversible model, our next step was to explore its intuitive computational power. We did so with the help of transition graphs. Such a graph has a vertex for every result set of the system. We first examined the transition graphs of ordinary reaction systems. They are somewhat limited: for an ordinary reversible reaction system, the transition graph is either a single vertex or a directed rooted tree with all the edges pointing away from the root. Then, we introduced of Reaction Systems Reversible with Lookbehind, a more fundamental twist on the base model: it allows the system to consider its most recent result and context set separately as opposed to only being capable of seeing their union (the current state). This results in a behavior similar to finite automata, drawing a parallel between the system's context and state set and the automata's input symbol and state. The state transition graphs of reversible finite transition systems correspond to the transition graphs of Reaction Systems Reversible with Lookbehind. Vice-versa, the transition graph of any Reaction System Reversible with Lookbehind corresponds to the state transition graph of a reversible finite transition system.

Our initial motivation was experimenting with different reversibility paradigms, so we focused on causal consistency after backtracking. The model of Reaction Systems is sequential without any concurrent behavior. Thus, we investigated Communicating Reaction Systems with Direct Communication, initially defined by Csuhaj-Varjú and Sethy. To enable concurrent behavior, we introduced our variant of Communicating Reaction Systems called Distributed Communicating Reaction Systems (d-cdcR Systems, for short). This model removes global synchronization by defining blocking computation and active components.

With the last obstacle, the lack of concurrency, out of the way, we implemented causal consistent reversibility to the model. We did so based on the axiomatic framework of Lanese, Phillips, and Ulidowski. This framework establishes axioms from which more involved properties, such as causal consistent reversibility, can be inferred.

Our implementation for causal consistent d-cdcR Systems comprises two layers. On the component level, we require local reversibility: each component must be reversible according to the results in Section~\ref{section::uncontrolled-backtracking}. Then, on the level of the system as a whole, we track the communicated symbols using stacks attached to each component.