BubbleStorm: Replication, Updates, and Consistency in Rendezvous Information Systems

Leng, Christof (2012)
BubbleStorm: Replication, Updates, and Consistency in Rendezvous Information Systems.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Preview

BubbleStorm: Replication, Updates, and Consistency in Rendezvous Information Systems - PDF
phd-thesis-leng-tuprints.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .
Download (4MB) | Preview

Item Type:

Ph.D. Thesis

Type of entry:

Primary publication

Title:

BubbleStorm: Replication, Updates, and Consistency in Rendezvous Information Systems

Language:

English

Referees:

Buchmann, Prof. Alejandro P. ; Kemme, Prof. Dr.- Bettina ; Wehrle, Prof. Dr.- Klaus

Date:

14 September 2012

Place of Publication:

Darmstadt

Date of oral examination:

22 August 2012

Abstract:

As distributed systems are getting more and more complex, search facilities for finding services and data within the system become crucial. Users expect search engines to deal with complex query languages like keyword search, SQL, or XPath. At the same time, application developers cannot be expected to come up with distributed versions of those query languages from scratch. Rendezvous search systems are a very scalable solution to this problem. By separating the query processing from the network communication, existing libraries for query processing can be easily reused. A wide range of rendezvous search systems for different scenarios has been proposed in the past. Their scalability and resilience make them an excellent choice for search in large-scale and dynamic peer-to-peer environments. The resilience stems mainly from the high number of replicas per datum, which however makes replica maintenance difficult. Unfortunately, most rendezvous search systems lack maintenance algorithms to sustain the desired replica count under node churn. Replica maintenance is closely related to update mechanisms for mutable data. The highly distributed nature of peer-to-peer systems in general and the high replica count of rendezvous search systems in particular require carefully designed mechanisms for consistent updates with concurrent accesses. In this thesis, replica maintenance and update mechanisms for the BubbleStorm peer-to-peer overlay and related rendezvous search systems are introduced. After analyzing the design space of replica maintenance for peer-to-peer systems, a complete solution covering all identified use cases is presented. This includes a maintainer-based mechanism for data managed by a single node and a collective mechanism for data that shall be persistent beyond any particular node’s session time. The algorithms are evaluated in BubbleStorm’s sophisticated testbed, which allows prototype experiments and simulations with the same source code.

Alternative Abstract:

Alternative Abstract

Language

Da verteilte Systeme immer komplexer werden, kommt Suchmechanismen zum Auffinden von Services und Daten eine stetig wachsende Bedeutung zu. Anwender erwarten, dass Suchmaschinen komplexe Anfragesprachen wie Volltextsuche, SQL oder XPath verarbeiten können. Gleichzeitig kann von Anwendungsentwicklern jedoch nicht erwartet werden, dass sie verteilte Versionen dieser Anfragesprachen von Grund auf selbst implementieren. Rendezvous-Suchsysteme stellen eine hochgradig skalierbare Lösung für dieses Problem dar. Durch die Trennung von Anfragebearbeitung und Netzwerkkommunikation können bestehende Implementierungen der Anfragesprachen leicht wiederverwendet werden. Eine breite Palette an Rendezvous-Suchsytemen wurde bereits für verschiedene Szenarien vorgeschlagen. Ihre Skalierbarkeit und Robustheit macht sie zu einer ausgezeichneten Wahl für die Suche in großen und dynamischen Peer-to-Peer-Umgebungen. Diese Robustheit basiert zu großen Teilen auf der hohen Anzahl von Replikaten pro Datum, wodurch allerdings die Replikaverwaltung erschwert wird. Leider fehlt den meisten Rendezvous-Suchsystemen eine Replikaverwaltung, welche die gewünschte Anzahl der Replikate bei Veränderungen der Netzwerkzusammensetzung aufrecht erhält. Die Replikaverwaltung ist eng verwandt mit Updatemechanismen für veränderliche Daten. Die verteilte und dezentrale Natur von Peer-to-Peer-Systemen im Allgemeinen und die hohe Anzahl von Replikaten in Rendezvous-Suchsystemen im Speziellen erfordern sorgfältig gestaltete Mechanismen für konsistente Updates bei konkurrierenden Zugriffen. In dieser Dissertation werden Replikaverwaltung und Updatemechanismen für das Peer-to-Peer-Overlay BubbleStorm und verwandte Rendezvous-Suchsysteme vorgestellt. Nach Analyse des Entwurfraums für die Replikaverwaltung in Peer-to-Peer-Systemen wird eine vollständige Lösung für alle identifizierten Anwendungsfälle präsentiert. Dies beinhaltet einen verwalterbasierten Mechanismus für Daten, die von einem einzelnen Knoten verwaltet werden, und einen kollektiven Mechanismus für Daten, welche über die Onlinezeit jedes einzelnen Knotens hinaus verfügbar bleiben sollen. Die Algorithmen werden mit BubbleStorms hoch entwickelter Testumgebung evaluiert, die es erlaubt, den selben Quellcode sowohl für Prototypenexperimente als auch für Simulationen zu verwenden.

German

URN:

urn:nbn:de:tuda-tuprints-30780

Classification DDC:

000 Generalities, computers, information > 004 Computer science

Divisions:

20 Department of Computer Science > Databases and Distributed Systems

Date Deposited:

22 Nov 2012 16:44

Last Modified:

07 Dec 2012 12:05

URI: