Show simple item record

AuthorErb, Benjamindc.contributor.author
Date of accession2020-02-13T15:44:31Zdc.date.accessioned
Available in OPARU since2020-02-13T15:44:31Zdc.date.available
Year of creation2019dc.date.created
Date of first publication2020-02-13dc.date.issued
AbstractModern applications with increasingly connected domain topologies require processing and programming abstractions that reflect the network structure inherent to these applications. At the same time, data-intensive applications necessitate more and more online processing capabilities when consuming incoming streams of events to execute continuous computations and provide fast results. Only very few systems have taken into account the combined challenge of executing graph processing on a dynamically evolving graph. However, this is a critical capability as timely computations enable reactive application behaviors upon graph changes. In addition, no existing system supports processing on a live graph and on past version of that evolving graph at the same time. The distinct characteristics of event processing and graph computing, as well as batch processing and live processing yield specific requirements for any computing platform that unifies these approaches. Solutions require (i) data management strategies to keep track of the continuous graph evolution, (ii) appropriate graph processing models that can simultaneously handle computations and graph updates, and (iii) an efficient platform implementation that provides the necessary performance at runtime. To this end, this thesis suggests a combination of an adapted actor model, an event-sourced persistence layer, and a vertex-based, asynchronous live programming model. The event-sourced actor model enables highly concurrent computations in which the full application history is implicitly persisted. This model is then refined into a live graph processing model with a particular focus on asynchronicity, liveness, and parallel execution support. At the same time, the use of event sourcing enables the model to reconstruct global and consistent graph representations from arbitrary points of the timeline. These graph representations form the basis for decoupled, non-live graph processing models. The Chronograph platform represents an implementation of the event-sourced graph model. The platform ingests external update streams and maintains a live graph representation as part of a user-specified graph application. It thus enables live and offline computations on event-driven, history-aware graphs and supports different processing models on the evolving graph. This thesis provides the following contributions: (i) a distributed computing approach with history support based on the actor model and event sourcing, as wall as corresponding and supplementary concepts, (ii) a data management approach for evolving graphs that builds on the event-sourced actor model, (iii) a set of novel and adapted programming and processing models that integrate well with event-sourced graphs, (iv) a distributed platform architecture that implements the event-sourced graph model; and (v) an evaluation framework for such live graph processing systems.dc.description.abstract
AbstractModerne Software-Systeme bilden immer komplexere Szenarien mit zunehmend vernetzteren Anwendungsdaten ab. Dies erfordert neue Verabreitungsmodelle, welche die Vernetzung der Daten miteinbezieht. Gleichzeitig erfordern datenintensive Anwendungen vermehrt eine echtzeitnahe Verarbeitung, um auf eingehenden Datenströmen kontinuierliche Berechnungen mit zeitnahen Berechnungen durchzuführen. Kaum ein System erlaubt bisher die Kombination beider Ansätze – kontinuierliche Berechnungen auf Graphen, die sich zugleich auf Basis von externen Ereignisströmen verändern. Dies ist jedoch eine wichtige Fähigkeit, wenn Anwendungen kontinuierlich auf dynamischen Graphen operieren und auf Veränderungen reagieren müssen. Zudem unterstützt keines der existierenden Systeme sowohl Berechnungen auf dem Live-Graph als auch auf älteren Versionen des Graphs. Ein solches System muss einerseits die Anforderungen von Event Processing und Graph Processing gegeneinander abwägen, als auch die Konzepte echtzeitnaher und stapelbasierter Berechnungen zusammenführen. Dies erfordert (i) Datenverwaltungsstrategien zur Verfolgung des sich entwickelnden Graphs, (ii) angemessene Ausführungsmodelle, die gleichzeitig Berechnungen und Graph-Änderungen verarbeiten können sowie (iii) eine Implementierung der Plattform, die zur Laufzeit die erforderliche Leistung bereitstellt. In dieser Arbeit wird die Kombination des Aktor-Modells, Event Sourcing, sowie einem vertex-basierten, asynchronen Programmiermodell vorgeschlagen. Das resultierende Modell ermöglicht ermöglicht hochgradig parallele Berechnungen bei gleichzeitiger Persisitierung der vollständingen Zustandshistorie de Aktoren. Dieses Modell dient als Grundlage für ein darauf aufbauendes Verarbeitungsmodell für Graphen mit besonderem Schwerpunkt auf Asynchronität, Reaktionsvermögen und Unterstützung der parallelen Ausführung. Gleichzeitig ermöglicht der Einsatz von Event Sourcing die konsistente und globale Rekonstruktion beliebiger Graph-Zustände aus der Zeitleiste, welche als Grundlage für weitere, entkoppelte Berechnungen. Chronograph implementiert als Plattform das konzeptuelle Modell und führt benutzerdefinierte Graph-Anwendungen auf sich ändernden Graphen aus. Externe Datenströme dienen dabei als Quelle für Änderungen, welche vom System direkt eingepflegt werden. Chronograph unterstützt gleichzeitig verschiedene Berechnungsmodelle, sowohl auf dem Live-Graphen, als auch auf älteren Graph-Versionen. Diese Arbeit bietet die folgenden Beiträge: (i) ein Konzept für verteilte, persistierte Berechnungen auf Basis des Aktor-Modells und Event Sourcing, (ii) ein darauf aufbauender Data-Management-Ansatz für sich ändernde Graphen, (iii) eine Reihe von neuartigen und darauf angepassten Programmier- und Verarbeitungsmodellen für Graphen, (iv) eine verteilte Plattformarchitektur, die das konzeptuelle Modell implementiert und (v) ein Framework zur Evaluation solcher Systeme.dc.description.abstract
Languageen_USdc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseStandarddc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/license_v3dc.rights.uri
KeywordGraph computingdc.subject
KeywordEvent sourcingdc.subject
KeywordBig data processingdc.subject
KeywordGraph processingdc.subject
KeywordEvent-sourced architecturesdc.subject
KeywordDistributed computingdc.subject
Dewey Decimal GroupDDC 004 / Data processing & computer sciencedc.subject.ddc
LCSHElectronic data processing Distributed processingdc.subject.lcsh
LCSHGraph labelingsdc.subject.lcsh
LCSHDistributed systemsdc.subject.lcsh
LCSHBig datadc.subject.lcsh
LCSHGP (Computer program language)dc.subject.lcsh
TitleDistributed computing on event-sourced graphsdc.title
Resource typeDissertationdc.type
Date of acceptance2019-12-04dcterms.dateAccepted
RefereeKargl, Frankdc.contributor.referee
RefereeRothermel, Kurtdc.contributor.referee
DOIhttp://dx.doi.org/10.18725/OPARU-25258dc.identifier.doi
PPN1690115335dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-oparu-25321-0dc.identifier.urn
GNDDCEdc.subject.gnd
GNDBig Datadc.subject.gnd
FacultyFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.affiliationGeneral
InstitutionInstitut für Verteilte Systemeuulm.affiliationSpecific
Grantor of degreeFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.thesisGrantor
DCMI TypeTextuulm.typeDCMI
CategoryPublikationenuulm.category
University Bibliographyjauulm.unibibliographie


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record