Wesley W. Terpstra
Abstract
Peer-to-peer systems promise inexpensive scalability, adaptability, and robustness. Thus, they are an attractive platform for file sharing, distributed wikis, and search engines. These applications often store weakly structured data, requiring sophisticated search algorithms. To simplify the search problem, most scalable algorithms introduce structure to the network. However, churn or violent disruption may break this structure, compromising search guarantees.
This paper proposes a simple probabilistic search system, BubbleStorm, built on random multigraphs. Our primary contribution is a flexible and reliable strategy for performing exhaustive search. BubbleStorm also exploits the heterogeneous bandwidth of peers. However, we sacrifice some of this bandwidth for high parallelism and low latency. The provided search guarantees are tunable, with success probability adjustable well into the realm of reliable systems.
For validation, we simulate a network with one million low-end peers and show BubbleStorm handles up to 90% simultaneous peer departure and 50% simultaneous crash.
- B. Bollobàs. Random Graphs. Cambridge University Press, 2nd edition, 2001.Google Scholar
- V. Bourassa and F. B. Holt. SWAN: Small-world wide area networks. In SSGRR, 2003.Google Scholar
- L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web Caching and Zipf-like Distributions: Evidence and Implications. In INFOCOM, pages 126--134, 1999.Google ScholarCross Ref
- Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker. Making gnutella-like P2P systems scalable. In SIGCOMM, pages 407--418, 2003. Google ScholarDigital Library
- C. Cooper, M. Dyer, and C. Greenhill. Sampling regular graphs and a peer-to-peer network. In SODA, pages 980--988, 2005. Google ScholarDigital Library
- P. T. Eugster, P. A. Felber, R. Guerraoui, and A. M. Kermarrec. The many faces of Publish/Subscribe. ACM Computing Surveys, 35(2):114--131, 2003. Google ScholarDigital Library
- R. A. Ferreira, M. K. Ramanathan, A. Awan, A. Grama, and S. Jagannathan. Search with Probabilistic Guarantees in Unstructured Peer-to-Peer Networks. In P2P, pages 165--172, 2005. Google ScholarDigital Library
- C. Greenhill, F. B. Holt, and N. Wormald. Expansion properties of a random regular graph after random vertex deletions, 2007. European Journal of Combinatorics (to appear). Google ScholarDigital Library
- K. P. Gummadi, R. J. Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, and J. Zahorjan. Measurement, Modeling and Analysis of a Peer-to-Peer File-Sharing Workload. In SOSP, pages 314--329, 2003. Google ScholarDigital Library
- D. Kempe, A. Dobra, and J. Gehrke. Gossip-Based Computation of Aggregate Information. In FOCS, pages 482--491, 2003. Google ScholarDigital Library
- J. Li, B. Loo, J. Hellerstein, F. Kaashoek, D. Karger, and R. Morris. On the feasibility of peer-to-peer web indexing and search. In IPTPS, 2003.Google ScholarCross Ref
- P. Maymounkov and D. Mazières. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. In IPTPS, pages 53--65, 2002. Google ScholarDigital Library
- P. Reynolds and A. Vahdat. Efficient peer-to-peer keyword searching. In Middleware, pages 21--40, 2003. Google ScholarDigital Library
- K. Sankaralingam, S. Sethumadhavan, and J. C. Browne. Distributed Pagerank for P2P Systems. In HPDC, pages 58--68, 2003. Google ScholarDigital Library
- S. Saroiu, P. K. Gummadi, and S. D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. In MMCN, 2002.Google Scholar
- N. Sarshar, P. O. Boykin, and V. P. Roychowdhury. Percolation Search in Power Law Networks: Making Unstructured Peer-to-Peer Networks Scalable. In P2P, pages 2--9, 2004. Google ScholarDigital Library
- W. W. Terpstra, C. Leng, and A. P. Buchmann. Brief Announcement: Practical Summation via Gossip. In PODC, 2007. Google ScholarDigital Library
- W. W. Terpstra, C. Leng, and A. P. Buchmann. BubbleStorm: Analysis of Probabilistic Exhaustive Search in a Heterogeneous Peer-to-Peer System. Technical Report TUD-CS-2007-2, Technische Universität Darmstadt, Germany, 2007.Google Scholar
- Wikimedia Foundation. What we need the money for. http://wikimediafoundation.org/w/index.php?title=What_we_need_the_money_for&oldid=18704Google Scholar
- K.-H. Yang and J.-M. Ho. Proof: A DHT-based Peer-to-Peer Search Engine. In Conference on Web Intelligence, pages 702--708, 2006. Google ScholarDigital Library
- Y. Yang, R. Dunlap, M. Rexroad, and B. F. Cooper. Performance of Full Text Search in Structured and Unstructured Peer-to-Peer Systems. In INFOCOM, 2006.Google ScholarCross Ref
Index Terms
- Bubblestorm: resilient, probabilistic, and exhaustive peer-to-peer search
Recommendations
Bubblestorm: resilient, probabilistic, and exhaustive peer-to-peer search
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communicationsPeer-to-peer systems promise inexpensive scalability, adaptability, and robustness. Thus, they are an attractive platform for file sharing, distributed wikis, and search engines. These applications often store weakly structured data, requiring ...
A resilient architecture for DHT-based distributed collaborative environments
SERENE '08: Proceedings of the 2008 RISE/EFTS Joint International Workshop on Software Engineering for Resilient SystemsDistributed Hash Tables (DHTs) provide a flexible and reliable infrastructure for data storage and retrieval in peer-to-peer communities. We propose to apply Kademlia DHT to organize data management and cooperation between users participating in ...
Analyzing and enhancing the resilience of structured peer-to-peer systems
In this paper, we propose an approach to analyze the resilience of structured peer-to-peer (P2P) systems under failures. The approach is Markov-chain based, and can be applied to systems with relatively stable size and uniform distribution of nodes. We ...
Comments