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.

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

Publications