TU Darmstadt / ULB / TUprints

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

Terpstra, Wesley W. :
BubbleStorm: Rendezvous Theory in Unstructured Peer-to-Peer Search.
E-Publishing-Service der TU Darmstadt, Darmstadt
[Ph.D. Thesis], (2015)

[img]
Preview
Text
thesis-20150720.pdf - Accepted Version
Available under Creative Commons Attribution Non-commercial No-derivatives 3.0 de.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Title: BubbleStorm: Rendezvous Theory in Unstructured Peer-to-Peer Search
Language: English
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
Place of Publication: Darmstadt
Publisher: E-Publishing-Service der TU Darmstadt
Uncontrolled Keywords: unstructured peer-to-peer rendezvous search
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Databases and Distributed Systems
Date Deposited: 29 Jul 2015 14:35
Last Modified: 29 Jul 2015 14:35
URN: urn:nbn:de:tuda-tuprints-46376
Referees: Buchmann, Prof Ph.D. Alejandro and Kangasharju, Prof. Dr. Jussi and Moody, Dr. Ken
Refereed: 23 January 2015
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/4637
Export:
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year