Peer-to-peer systems consist of hundreds to millions of computers, which work together to solve a common problem. In contrast to their more common client-server counterparts, peer-to-peer algorithms try to exploit the resources of all participants. The potential advantage to this approach is improved reliability, scalability, and load balance. Applications for these systems are still emerging, but notoriously include file distribution, wireless sensor networks, and keyword search.
Fundamentally, a distributed system of cooperating computers must implement some policy for organizing the group. The BubbleStorm approach is to use randomized processes to probabilistically organize the participants. Peers in the system follow simple, local-only rules about who they talk to and when. These rules are chosen so that the emergent system behaviour can be used to solve useful problems. The correct output of the system can then be modelled as a random event in a Markov process. As peer-to-peer systems are already so large as to practically guarantee that some components fail, probabilistic correctness and availability guarantees seem reasonable.
A network topology describes how the cooperating computers interact. Many modern peer-to-peer systems implement a so-called distributed hash table (DHT) interface. Typically they view the network as a superposition of routing trees, one for each participant. Unfortunately, due to the dynamic nature of the system, these trees often become disconnected, compromising the correctness. Participants in DHTs are also usually given more-or-less equal roles; it is difficult to leverage heterogeneity (participants with different resources). Naturally, DHTs apply many heuristics to solving these problems, but no existing DHT systems provides even probabilistic guarantees.
The BubbleStorm topology consists instead of a random, fixed degree sequence graph. In such a topology, every participant decides on his degree (number of people to talk to) and chooses that many neighbours uniformly at random. As there is no need to maintain a particular tree shape, the topology can easily cope with component failure by reconnecting to different participants. Due to a well-known theorem about random walks, each participant receives work proportional to his degree, allowing a natural load balancing for heterogeneous systems. For these reasons, BubbleStorm delivers better on the peer-to-peer promise of reliability and load balance.
Example propagation of a blue and green message till intersection
Naturally, a peer-to-peer system must ultimately solve its problem. High-level problems are often posed as publish-subscribe and query-document. DHTs implement these high-level problems by forcing them into a key-value abstraction. BubbleStorm solves them directly by blowing bubbles (range limited flooding), one bubble for each publication (or document) and another for each subscription (or query). The advantage to the BubbleStorm approach is that no restrictions are placed on the query language. As DHTs must use the hash table interface, this restricts the subscription language to so-called 'topics'. Attempts to apply DHTs to keyword search are also problematic it does not easily fit into the key-value abstraction. All the participants within a bubble receive the document meta-data or query. Any participant in both bubbles can answer the query for that document directly, regardless of the query language.
Scalability is a major concern for peer-to-peer systems. While DHTs achieve (when everything goes according to plan) an O(log n) message complexity, BubbleStorm requires O(sqrt(n)). Though this may seem very undesirable, one must realize that we are comparing apples to oranges. A DHT can only solve a key-value query, whereas BubbleStorm can solve any query. When the query language cannot be easily partioned, the problem becomes a distributed cartesian product. Indeed, to solve these more difficult problems (like keyword search) the real complexity of a DHT approach is much higher and hard to explicitly derive. We have proved lower-bound results that show that any system solving distributed cartesian product (which BubbleStorm does), must spend at least as many messages as BubbleStorm. Therefore, BubbleStorm is in some sense optimal for the problems which need it, achieving the best scalability one could hope for.
Resources
The BubbleStorm source code is available on GitHub!Publications
BubbleStorm: Replication, Updates, and Consistency in Rendezvous Information Systems (PhD Thesis) Christof Leng Technische Universität Darmstadt, Darmstadt, Germany, TU Prints, August 2012 [PDF] [BibTeX] |
Distributed Search with Rendezvous Search Systems Christof Leng 7th KuVS/ITG-Fachgespräch Future Internet, Munich, Germany, January 2012 [PDF] [Slides] [BibTeX] |
Distributed SQL Queries with BubbleStorm Christof Leng, Wesley W. Terpstra In Kai Sachs, Ilia Petrov, Pablo Guerrero: From Active Data Management to Event-Based Systems and More, Lecture Notes in Computer Science 6462, ISBN 978-3-642-17225-0, Springer, November 2010 [PDF] [BibTeX] |
Maintaining Replicas in Unstructured P2P Systems Christof Leng, Wesley W. Terpstra, Bettina Kemme, Wilhelm Stannat, Alejandro P. Buchmann Proceedings of the 4th ACM International Conference on emerging Networking EXperiments and Technologies (ACM CoNEXT 2008), Madrid, Spain, December 2008 [Conference] [PDF] [BibTeX] |
Brief Announcement: Practical Summation via Gossip Wesley W. Terpstra, Christof Leng, Alejandro P. Buchmann Twenty-Sixth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2007), Portland, Oregon, USA, August 2007 [PDF] [PS] [Slides] [BibTeX] |
BubbleStorm: Resilient, Probabilistic, and Exhaustive Peer-to-Peer Search Wesley W. Terpstra, Jussi Kangasharju, Christof Leng, Alejandro P. Buchmann Proceedings of the 2007 ACM SIGCOMM Conference, Kyoto, Japan, August 2007 [Conference] [PDF] [PS] [Slides] [BibTeX] |
BubbleStorm: Analysis of Probabilistic Exhaustive Search in a Heterogeneous Peer-to-Peer System Wesley W. Terpstra, Christof Leng, Alejandro P. Buchmann Technical Report, No. TUD-CS-2007-2, Technische Universität Darmstadt, Fachbereich Informatik, Darmstadt, Germany, May 2007 [PDF] [BibTeX] |