TU Darmstadt / ULB / TUprints

BubbleStorm: Rendezvous Theory in Unstructured Peer-to-Peer Search

Terpstra, Wesley W. (2015)
BubbleStorm: Rendezvous Theory in Unstructured Peer-to-Peer Search.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
Text
thesis-20150720.pdf - Accepted Version
Copyright Information: CC BY-NC-ND 3.0 Unported - Creative Commons, Attribution, NonCommercial, NoDerivs.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: BubbleStorm: Rendezvous Theory in Unstructured Peer-to-Peer Search
Language: English
Referees: Buchmann, Prof Ph.D. Alejandro ; Kangasharju, Prof. Dr. Jussi ; Moody, Dr. Ken
Date: 23 January 2015
Place of Publication: Darmstadt
Publisher: E-Publishing-Service der TU Darmstadt
Date of oral examination: 23 January 2015
Abstract:

This thesis presents BubbleStorm, which attempts to bridge the gap between peer-to-peer and databases. BubbleStorm is a peer-to-peer search system, which solves large-scale rendezvous problems over the unreliable global internet. It provides a concept of user-defined bubble types, loosely corresponding to table schemas. Queries follow the fully general black-box model, allowing powerful queries to be evaluated exhaustively. The system tracks usage statistics with a system-wide measurement service, used to automatically tune search performance. As strong consistency guarantees are impossible, BubbleStorm instead aims for user-controlled probabilistic guarantees.

The key contribution of this thesis is to develop rendezvous theory and reformulate the black-box query model within this framework. This reformulation allows us to interpret any black-box system as solving a rendezvous problem, allowing an elegant and tight lower-bound. BubbleStorm leverages rendezvous theory to substantially reduce bandwidth consumption (both practically and asymptotically) while simultaneously improving query latency. The resulting system, which has a full fledged implementation, sports a simple to understand interface, which abstracts away the underlying details, much like the database systems before it.

Alternative Abstract:
Alternative AbstractLanguage

Diese Arbeit präsentiert das BubbleStorm-System, welches versucht, die Lücke zwischen Peer-to-Peer-Netzwerken und Datenbanken zu schließen. BubbleStorm ist ein Peer-to-Peer-Suchsystem, das großangelegte Rendezvous-Probleme im unzuverlässigen globalen Internet löst. Es bietet ein Konzept der benutzerdefinierten Bubble-Typen, die grob Tabellenschemata entsprechen. Abfragen folgen dem völlig allgemeinen Black-Box-Modell, um die vollständige Auswertung komplexer Abfragen zu ermöglichen. Das System benutzt Nutzungsstatistiken, erstellt von einem systemweiten Messdienst, um automatisch die Suchleistung zu optimieren. Da starke Konsistenz-Garantien beweisbar ausgeschlossen sind, strebt BubbleStorm stattdessen nach benutzergesteuerten probabilistischen Garantien.

Der Hauptbeitrag dieser Arbeit ist die Entwicklung der Rendezvous-Theorie und Abfragen des Black-Box-Modells im Rahmen der Rendezvous-Theorie umzuformulieren. Diese Neuformulierung ermöglicht es, jedes Black-Box-System als Lösung eines Rendezvous-Problems zu betrachten, woraus eine elegante und enge Untergrenze folgt. Bubblestorm setzt Rendezvous-Theorie wirksam ein, um den Bandbreitenverbrauch (sowohl praktisch als auch asymptotisch) erheblich zu reduzieren, während die Latenz gleichzeitig verbessert wird. Das resultierende System, das eine vollwertige Implementierung hat, unterstützt ein konzeptionell einfaches Interface, das die darunterliegenden Details abstrahiert, vergleichbar mit den vorhergehenden Datenbanksystemen.

German
Uncontrolled Keywords: unstructured peer-to-peer rendezvous search
URN: urn:nbn:de:tuda-tuprints-46376
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Databases and Distributed Systems
Date Deposited: 29 Jul 2015 14:35
Last Modified: 29 Jul 2015 14:35
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/4637
PPN: 362663866
Export:
Actions (login required)
View Item View Item