File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Gossipbased publishsubscribe systems in peertopeer networks
Title  Gossipbased publishsubscribe systems in peertopeer networks 

Authors  
Advisors  Advisor(s):Yeung, LK 
Issue Date  2014 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Zhang, X. [张昕]. (2014). Gossipbased publishsubscribe systems in peertopeer networks. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5351050 
Abstract  Peertopeer (P2P) paradigm, for its scalability and low cost management, is widely used in today’s network. Based on the typical designs for request/response services, a lot of efforts have been made to support publishsubscribe services in P2P networks. Gossipbased publishsubscribe system, which is commonly used in unstructured P2P networks, can provide great flexibility in query language and does not require special efforts on maintaining topology. The purpose of our work is to investigate effective and efficient mechanisms to build gossipbased publishsubscribe systems in unstructured P2P networks. Specifically, the probabilistic biquorum system (PBQS), for its assurance in effectiveness, becomes the object of our study.
Uniform sampling is a fundamental tool to construct PBQS. By adopting uniform sampling, PBQS provides a bound on the likelihood that data messages will find a copy of the subscription. A random walk of length O(log n) is commonly used to gain a uniform sample on an expander graph of size n. To obtain a multitude of uniform samples thus requires an equivalent number of random walks of length O(log n) each. A number of works have relied on the Chernoff bound to analytically reduce the overhead needed to obtain a multitude of uniform samples. Besides, researchers have also shown that it is not necessary to replicate both data and query on uniformly chosen nodes. Alternatively, BubbleStorm performs controlled flooding on a constructed overlay to build PBQS. BubbleStorm does not require nodes forming a bubble to be uniformly chosen at random, and the probabilistic bound computed by BubbleStorm is different from uniform sampling based PBQS.
In this thesis, we first show that the Chernoff bound on the statistical properties of samples collected from a random walk does not help in selecting uniformly random nodes. We then reexamine the role of uniform sampling in PBQS, and found that when multiple data answer a single subscription, it is sufficient and necessary for each data to be distributed uniformly at random. Looking into BubbleStorm, we examine more closely the probabilistic bound provided by this system. We found that, unlike uniform sampling based PBQS, the bubble intersection in BubbleStorm is distance dependent. Given a specific pair of publishersubscriber, the data may never find the subscription. We further investigate the topology construction and found that recreating topology prior to each controlled flooding or keeping topology with high degree of churn can help alleviate the distance dependency problem. We arrive at the conclusion that BubbleStorm construction is equivalent to caching of random walks. We show that reusing this cache to obtain samples over time leads to degradation of uniformity of the samples. We evaluate topology rewiring as a simple method to keep the cache fresh, thereby benefiting from the low latency of controlled flooding without degrading the uniformity of samples over time. 
Degree  Master of Philosophy 
Subject  Push technology (Computer networks) Peertopeer architecture (Computer networks) 
Dept/Program  Electrical and Electronic Engineering 
Persistent Identifier  http://hdl.handle.net/10722/208013 
HKU Library Item ID  b5351050 
DC Field  Value  Language 

dc.contributor.advisor  Yeung, LK   
dc.contributor.author  Zhang, Xin   
dc.contributor.author  张昕   
dc.date.accessioned  20150206T14:19:34Z   
dc.date.available  20150206T14:19:34Z   
dc.date.issued  2014   
dc.identifier.citation  Zhang, X. [张昕]. (2014). Gossipbased publishsubscribe systems in peertopeer networks. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5351050   
dc.identifier.uri  http://hdl.handle.net/10722/208013   
dc.description.abstract  Peertopeer (P2P) paradigm, for its scalability and low cost management, is widely used in today’s network. Based on the typical designs for request/response services, a lot of efforts have been made to support publishsubscribe services in P2P networks. Gossipbased publishsubscribe system, which is commonly used in unstructured P2P networks, can provide great flexibility in query language and does not require special efforts on maintaining topology. The purpose of our work is to investigate effective and efficient mechanisms to build gossipbased publishsubscribe systems in unstructured P2P networks. Specifically, the probabilistic biquorum system (PBQS), for its assurance in effectiveness, becomes the object of our study. Uniform sampling is a fundamental tool to construct PBQS. By adopting uniform sampling, PBQS provides a bound on the likelihood that data messages will find a copy of the subscription. A random walk of length O(log n) is commonly used to gain a uniform sample on an expander graph of size n. To obtain a multitude of uniform samples thus requires an equivalent number of random walks of length O(log n) each. A number of works have relied on the Chernoff bound to analytically reduce the overhead needed to obtain a multitude of uniform samples. Besides, researchers have also shown that it is not necessary to replicate both data and query on uniformly chosen nodes. Alternatively, BubbleStorm performs controlled flooding on a constructed overlay to build PBQS. BubbleStorm does not require nodes forming a bubble to be uniformly chosen at random, and the probabilistic bound computed by BubbleStorm is different from uniform sampling based PBQS. In this thesis, we first show that the Chernoff bound on the statistical properties of samples collected from a random walk does not help in selecting uniformly random nodes. We then reexamine the role of uniform sampling in PBQS, and found that when multiple data answer a single subscription, it is sufficient and necessary for each data to be distributed uniformly at random. Looking into BubbleStorm, we examine more closely the probabilistic bound provided by this system. We found that, unlike uniform sampling based PBQS, the bubble intersection in BubbleStorm is distance dependent. Given a specific pair of publishersubscriber, the data may never find the subscription. We further investigate the topology construction and found that recreating topology prior to each controlled flooding or keeping topology with high degree of churn can help alleviate the distance dependency problem. We arrive at the conclusion that BubbleStorm construction is equivalent to caching of random walks. We show that reusing this cache to obtain samples over time leads to degradation of uniformity of the samples. We evaluate topology rewiring as a simple method to keep the cache fresh, thereby benefiting from the low latency of controlled flooding without degrading the uniformity of samples over time.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.subject.lcsh  Push technology (Computer networks)   
dc.subject.lcsh  Peertopeer architecture (Computer networks)   
dc.title  Gossipbased publishsubscribe systems in peertopeer networks   
dc.type  PG_Thesis   
dc.identifier.hkul  b5351050   
dc.description.thesisname  Master of Philosophy   
dc.description.thesislevel  Master   
dc.description.thesisdiscipline  Electrical and Electronic Engineering   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b5351050   