New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Special Topics

by: Alayna Veum
Alayna Veum

GPA 3.81

Ling Liu

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Ling Liu
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 8803 at Georgia Institute of Technology - Main Campus taught by Ling Liu in Fall. Since its upload, it has received 12 views. For similar materials see /class/234076/cs-8803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

Similar to CS 8803 at

Popular in ComputerScienence


Reviews for Special Topics


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15
PeerCQ A Decentralized and Self O O O configuring P2P Information Monitoring System Bugra Gedik Ling Liu CoC GaTech 2002 Georgia aas mu xe TechLuo ogy OOO Talk Outline I Information Monitoring I PeerCQ Overview I Service Partitioning I Fault Tolerance I Cost Analysis I Experimental Results I Conclusion amp Future Work O O 0 Information Monitoring Why I Everyone today can publish information on the web independently and at any time I Information sources are constantly and rapidly changing I Information sources are heterogeneous and autonomous noncooperating I There is a higher latency between change notification and source changes I Needs techniques for efficient execution of longrunning distributed queries and long standing distributed triggers wTechmg ccgy Georgia ms mu e Continual Queries and Information Monitoring I Continual Queries CQs are primitives used to express information monitoring requests I CQs are standing queries that monitor information updates and return results whenever the updates reach certain speci ed thresholds I There are three main components of a CO query trigger and stop condition Continual Query Q Trigger STOP Weather Q Altemative transport routes Infomlation 39 Trigger heavy Wind or rain STOP three months Monitor the weather in the region of port of Smannah and Atlanta Find all alternate transport routes when the weather Condition is bad hem2 wind or hem2 rain Continu al Query Centralized Information Monitoring COO OpenCQ WebCQ NiagaraCQ I Scaling requires both 0 Powerful servers or clusters 0 I ncreased network bandwidth Single point of failure P2P Alternative processing bottleneck network bottleneck Centralized Serve P2P Approach to Information Monitoring 555525 I P2P Information Monitoring 0 No central point of failure 0 Resources grow with 4 clients Network bandwidth Processing power I No administrative management cost O O O PeerCQ An Overview I The rst decentralized Internet scale P2P continual query system for monitoring information change on the web I PeerCQ o accepts CQs from peers o distributes CQs to appropriate peers o executes CQs at peers O 0 9 A Walkthrough Scenario PeerCQ serventepplicetinn an PeerA Noti cation a ager direct noti cation em all noti cation Internet P2P Protocol co Migration Natl cation Module Manager Manager cQ Replication co Processing Module Manager including co enuine an result cechE a Georgia ms e wTechmg ocgy O O 0 Challenges in PeerCQ I Assignment of CQs to Peers Service Partitioning o Balancing peer loads Peer heterogeneity o Utilizing system resources CQ grouping CQs interested in monitoring same data items can be grouped to decrease overall resource consumption including network bandwidth and repeated computation CQpeer coupling peer loads network proximity of peers to data sources I Providing a reliable system on top of a highly unreliable network of peers I Maintaining decentralization O O 0 Service Partitioning I Service partitioning Distribution of CQs to peers in a way that balances the load and improves system resource utilization Important features of PeerCQ service partitioning o Peerawareness o CQawareness 0 Efficient service lookup Geo ia wTregchmg Service lookup and service partitioning OOO Design choice DHT based Chordlike vs flooding based Gnutellalike o Flooding costly no restriction on where a CO can be executed locating the peer that will execute a CO is costly o DHT based efficient guaranteed lookup restricts where a CO can be executed suitable for replication amp fault tolerance PeerCQ service partitioning extends a Pastrylike DHT based P2P approach The assignments of CQs to peers are based on a matching algorithm defined between CQs and peers derived from a relationship between CQ identifiers and peer identifiers OO 0 Mapping Peers to Identifiers Map each peer to a set of unique mbit identifiers which forms that peer s identifier set I This mapping has to be as uniform as possible I The peers that donate more resources are assigned more peer identifiers virtual peer identifiers O Identifiers of Pa O Identifiers of Pb Geo ia wTregchmg How to define the number of Virtual Identifiers Define a measure called Effective Donation ED and calculate its value for each peer based on 0 amount of resources it wants to donate to the system and o the average amount oftime it stays in the network per session Donated resources are used to calculate the ED value ED is used to calculate the number of peer identifiers ED value is used to differentiate heterogeneous peers however it does not ensure that the system will not consume more than the donated resources O O 0 Mapping 005 to Identifiers I Each CO is assigned to an mbit identifier which is composed of two parts 0 the first part is same for CQs interested in monitoring the sama data item 0 the remaining part is uniquely random I The length of the first part is 3 also called the grouping factor I The identifier space is divided into 25 contiguous regions Based on its trigger a CO is mapped to an identifier in one of these regions Triggers defined on the same data item ldentlfler space O O 0 Matching 005 to Peers Strict Matching Phase 0 A CO is matched to a peer such that the peer has the peer identifier which is the closest one to the CO identifier This is a DHT lookup o The peer is called the CO owner I Relaxed Matching Phase 0 The CO owner carries out a search among peers having identifiers in its identifier neighborhood to nd a better qualified peer to execute the CO using three measures cache af nity factor peer load factor data source distance factor 0 The peer is called the CO executor Formulating the Relaxed Matching O O O Fu n ction Cache affinity factor CAFltvaq 1 cqmon7ifieme prache 0 o termse Peer load factor l d gt h MAX LOAD EL Strict matching PLFp 17 Flow p 0a res 7 W LOAD otherWiSB Source distance factor 1 SDF c p q pingitimecqmon7vrcpIP Relaxed matching function RMFpcq PLFp CAFpcqOzSDFpcq TecIm G Georgiana Formulating the Relaxed Matching Function Cache affinity factor 000 1 cqmon itemepcache CAMPch 0 otherwise re axed mg Peer load factor E Strict matching PLFp 17 glam p load g fresh T MAXiLOAD 5 W7 LOAD harms Source distance factor SDF C p q pingitimecqmon7vrcpIP Relaxed matching function RMFpcq PLFp CAFpcqOzSDFpcq O O 0 Service Lookup Details I Use Plaxton Routing and a Chordlike ring Logarithmic time in hops to insert and update CQs Each node maintains routing tables and neighbor lists one for each identifier they possess O O 0 Node Dynamics Node additions and deletions 0 Routing layer issues Routing table and neighbor list are correctly maintained 0 Service partitioning issues The strict matching and the relaxed matching are preserved for every CQ CQ owners and executors are changed properly to maintain the two matchings details in the paper O O 0 Fault Tolerance I Use replication for fault tolerance I Dynamic Passive replication 0 Backups Replica holders peers in the neighbor list of CO owner 0 Primary CQ executor determined based on relaxed matching Ropllmlinntisllqu stnchnarclwlcqlpl relaxed marrhkqlalptp venllme m O O 0 Cost Model Measures of interest 0 Load on a peers due to CO executions 0 Balance in loads of eers 0 Network load due to CO executions Notations P denote the network consisting of N peers G 91 is the set of groups that peer p has sizeGp n is the number of CO groups that peer has 9 represents a group in p which can be identi ed by its trigger identi er sizeg is the number of CQs group gy contains costg is the cost of processing all CQs in group gy thostg is the cost of executing group g s trigger ngostsizeg is the cost of grouping for group g costGp is the cost of processing all CQs in a peer balance denotes the load balance of the peers netCostp ds is a function that assigns costs to peer data source pairs based on the ping time between the peer and the data source avgNetCost denotes the average network cost O O 0 Cost Model cont loadp ostGp EDp was mm costGp Z costgl Z Costsizegl 11 21 5 may costGp sz39zeGp monCost Z gCostsizegl 11 balance VARload p E load p SIZE G ZFEPZIJ P netCostp gI monisrc avgNetCost N O O 0 Effect of Grouping cont tumva Setting the grouping factor a to higher values will decrease the number of CO groups processed by a peer while Optimized relaxed matching provides better grouping Peers 10000 5 data Srcs 5000 items 0 m Simulation Based o O 0 Experimental Results m quottritium quot mum xlu n quotaw w Effect ol mowing arm of grouping mm Hominich frcmmncy sri 9 t hmm v 39 5 c 7 u a no 9mm w pnrr a 0150 mm pm My Setting the grouping factor a to higher values will ecrease the number of CO groups processed by a peer while but may 39 quot 39 quotquot information monitoring requests Peers 10000 COs 1000000 data srcs 5000 items 0 Georg 1 TechLm m 128m O O 0 System Utilization R2n am my aim quotelm39k CD QDltlml1Dd Relaxm Milth mean load quotmark cost mun rm lumpan 1mm gmupmg factor Increasing the grouping factor helps in 39 quot luau 39 quot quot L 39 by enabling more group processing decreasingthe average network cost since the cost of fetching data items of interest from remote data sources is incurred only once per CQ group Optimized relaxed matching provides better utilization Peers 10000 s 1000000 0 data srcs 500 items 0 m 128rblt O O 0 Load Balance m mm laid an halal 4 s a muv l incth For moderate values ofthe grouping factor a the optimized relaxed matching provides betterload balance since it explicitly considers peer loads in its value 39 For high values ofthe grouping factor a the optimized relaxed matching provides worse load balance due to excessive grouping Higher values ofthe grouping factor a are better for favoring overall system utilization whereas lower values are better for favoring load balance peem 10000 it COS it data Bros 5000 it items 1 O O 0 Conclusions Information monitoring is an interesting and suitable application domain for applying P2P technology Mechanisms used for identi er mapping strict matching by considering resource and runtime factors when assigning CQs to peers relaxed matching is an effective way to provide reasonable system resource utilization and peer load balance PeerCQ home httpdislccgatecheduPeerCQ


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.