TY  - THES
AB  - Transaktionaler Speicher (TS) ist ein Konzept zur Kontrolle von Nebenläufigkeit, das die Zugriffe von mehreren Threads auf geteilten Speicher verwaltet. Threads können Transaktionen ausführen, die vom Speicher lesen und auf ihn schreiben können. Jede Transaktion soll nach außen so aussehen, als ob sie in einem atomaren Block ausgeführt wurde. Trotzdem kann eine TS Implementation mehrere Transaktionen nebenläufig ausführen solange nach außen hin die Ausführung korrekt erscheint. Es gibt mehrere Korrektheitsbedingungen, die formalisieren was "nach außen hin korrekt erscheinen" bedeutet. Obwohl schon viele Ansätze für das Überprüfen, ob einzelne Ausführungen oder ganze Implementationen von TSs diesen Bedinungen genügen, vorgestellt wurden, ist den zugrundeliegenden theoretischen Problemen weniger Aufmerksamkeit zuteilgeworden. Diese sind das Membershipproblem (überprüfen, ob eine einzelne Ausführung korrekt ist) und das Correctnessproblem (überprüfen, ob alle Ausführungen einer Implementation korrekt sind). In dieser Arbeit geben wir einen detaillierten Überblick über die existierenden Ergebnisse zur Komplexität dieser Probleme und präsentieren zwei eigene Ergebnisse für jedes dieser Probleme. Die Korrektheitsbedingungen, auf die wir uns hier konzentriert haben, sind Strict State Serializability (SSR) und Value Opacity (VO). Wir zeigen durch eine Reduktion von State Serializability, eine weniger strenge Version von SSR, dass das Membershipproblem für VO NP-vollständig ist. Außerdem präsentieren wir Annahmen, unter denen das Membershipproblem für VO äquivalent zu dem für Conflict Opacity, eine simplere Variante von VO, ist. In Bezug auf das Correctnessproblem zeigen wir seine Entscheidbarkeit für SSR und VO unter einschränkenden Annahmen.
AU  - König, Jürgen
CY  - Paderborn
DA  - 2023
DO  - 10.17619/UNIPB/1-1858
DP  - Universität Paderborn
LA  - ger
N1  - Tag der Verteidigung: 26.09.2023
N1  - Universität Paderborn, Dissertation, 2023
PB  - Veröffentlichungen der Universität
PY  - 2023
SP  - 1 Online-Ressource (xii, 296 Seiten)
T2  - Institut für Informatik
TI  - On the membership and correctness problem for state serializability and value opacity
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-46202
Y2  - 2026-01-21T09:55:06
ER  -