Object Location in More Realistic Networks

Object Location in More Realistic Networks

Tapestry: Finding Nearby Objects in Peer-to-Peer Networks Joint with: Ling Huang Anthony Joseph Robert Krauthgamer John Kubiatowicz Satish Rao Sean Rhea Jeremy Stribling Ben Zhao Object Location Behind the Cloud Why nearby? (DHT vs. DOLR) Nearby= low stretch, ratio of distance traveled to

find object to distance to closest copy of object Objects are services, so distance isnt one-time cost (see COMPASS) (smart) publishers put objects at chosen locations in network Bob Miller places retreat schedule at node in Berkeley Wildly popular objects Well-Placed Objects Popular Objects Outline Low stretch dynamic peer-to-peer network Tolerate failures in network Adapting to network variation Future work

Distributed Hash Tables System Neighbor Motivating s Structure Hops CAN, 2001 O(r) grid O(rn1/r) Chord, 2001

O(log n) hypercube O(log n) Pastry, 2001 O(log n) hypercube O(log n) Tapestry, 2001 O(log n)

hypercube O(log n) These systems give Guaranteed location Join and leave algorithms Load-balanced storage No stretch guarantees Low Stretch Approaches System Stretch Space Balanced

Metric Awerbuch Peleg, 1991 polylog polylog no General PRR, 1997 O(1) O(log n)

yes Special Thorup-Zwick O(k2) O(kn1/k) yes General RRVV, 2001 polylog

polylog yes General Not dynamic Tapestry is first dynamic low-stretch scheme PRR/Tapestry Country State City PRR/Tapestry

Level 3 Level 2 Level 1 Two object types: red and blue, so two trees Balancing Load Neighbor Table For 5471 (Octal) NodeID 5416 NodeID 5455 3 3

3 NodeID 5432 2 NodeID 5471 4 2 NodeID 5470 NodeID 5061 2

NodeID 5123 5470 540x 50xx 0xxx 5471 541x 51xx 1xxx

5472 542x 52xx 2xxx 5473 543x 53xx 3xxx 544x

54xx 4xxx 5475 545x 55xx 5xxx 546x 56xx

6xxx 5477 547x 57xx 7xxx 4 3 2 1 Routing Levels

1 Big Challenge: Joining Nodes Theorem 1 [HKRZ02] When peer A is finished inserting, it knows about all relevant peers that have finished insertion. Results Correctness O(log n) insert & delete Concurrent inserts in a lock-free fashion Neighbor-search routine Required to keep low stretch All low-stretch schemes do something like this Zhao, Huang, Stribling, Rhea, Joseph & Kubiatowicz (JSAC) This works! Implemented algorithms

Measured performance Neighbor Search In growth-restricted networks (with no additional space!): Theorem 2 [HKRZ02] Can find nearest neighbor with high probability with O(log2 n) messages Theorem 3 [HKMR04] Can find nearest neighbor, and messages is O(log n) with high probability Outline Low stretch dynamic peer-to-peer network Tolerate failures in network Adapting to network variation Future work

Behind the Cloud Again Dealing with faults Multiple paths Castro et. al One failure along path, path breaks Wide path Paths faulty at the same place to break Exponential difference in width effect retrofit Tapestry to do latter in slightly malicious networks Failed!

Still good Effective even for small overhead 100 90 % failed routes 80 1 2 3 4 5 6 70

60 50 40 30 20 10 0 0.1 0.2 0.3 0.4 0.5 Fraction of Bad Nodes

Theorem 4 In growth restricted spaces, can make probability of failed route less than 1/nc for width O(clog n) Hildrum & Kubiatowicz, DISC02 Wide path vs. multiple paths 90 80 4 4 Single Failed Paths 70 60 50 40 30 20

10 0 0 0.1 0.2 0.3 Fraction of Bad nodes 0.4 0.5 0.6 Outline

Low stretch dynamic peer-to-peer network Tolerate failures in network Adapting to Network Variation Future work Digit size affects performance 600 500 Work 400 300 200

100 0 0 5 10 15 Base 20 25 Network not homogeneous Previous schemes picked a digit size How do we find a good one?

But what if there isnt one? Nebraska Paris San Francisco New Result Pick digit size based on local measurements Dont need to guess Vary digit size depending on location No, its not obvious that this works, but it does! Hildrum, Krauthgamer & Kubiatowicz [SPAA04]: Dynamic, locally optimal low-stretch network

Conclusions and Future Work Conclusion Low stretch object location is practical System provably good [HKRZ02] System built [ZHSJK] Open Questions Do we need a DOLR? Object placement schemes? Workload? Examples where low stretch, load balance, and low storage not possible simultaneously What is tradeoff between degree, stretch, load balance as function of graph? Can we get best possible? Trade off smoothly? Tapestry People

Ling Huang Anthony Joseph John Kubiatowicz Sean Rhea Jeremy Stribling Ben Zhao andOceanStore group members

Recently Viewed Presentations

  • ISA 201 Intermediate Information Systems Acquisition

    ISA 201 Intermediate Information Systems Acquisition

    There is no right answer. The Navy has Categorization guidance for various information types. Note: NIST SP 800-60 also provides provisional impact levels for various information types but with caveats that this is only the first step in the analysis.
  • Lord of the Flies By William Golding - Cintra's Class

    Lord of the Flies By William Golding - Cintra's Class

    metaphor. personification- A figure of speech in which human qualities are attributed to an object, animal, or idea. foreshadowing-A writer's use of hints or clues to indicate events that will occur later in a story. ... Lord of the Flies...
  • Soldier for Life Overview LTC Jon Sowards Director,

    Soldier for Life Overview LTC Jon Sowards Director,

    Soldier for Life Campaign . Mission. Soldier for Life . connects. Army, governmental, and community efforts to build relationships that facilitate successful reintegration of our Soldiers, Retired Soldiers, Veterans, and their Families in order to keep them Army Strong and...
  • Maryland Department of Health / Marylands Commitment to

    Maryland Department of Health / Marylands Commitment to

    Since 1919, Easter Seals has been serving the community by providing assistance with physical, mental, and emotional health issues. In 2017, we formed a partnership with the Cohen Veterans Network to provide on-site mental health services in DC metro area.
  • Drug Court Counsel

    Drug Court Counsel

    Ethical considerations for each role on the Treatment Court Team. Work as a team. Mind your boundaries. Keep your ethics. Helen Harberts JD Chico CA
  • Telomerase and Radiosensitivity

    Telomerase and Radiosensitivity

    telomerase RNA (hTR) Telomere-associated . proteins . Telomerase, which are activated in 90% of human tumor cells but are seldom activated in normal somatic cells, is composed of two components, human telomerase RNA(hTR) and hTERT. The expression of hTERT, closely...
  • DISTANCE EDUCATION AND LEARNING TECHNOLOGY APPLICATIONS squirre Keep

    DISTANCE EDUCATION AND LEARNING TECHNOLOGY APPLICATIONS squirre Keep

    Moodle settings. UN-check for student view. Category with weight 0 for non-gradable content types. ... H5P for Moodle - User Guide. go.ncsu.edu/H5Pguide. How to get started. Brame, C., (2016). Active learning. Vanderbilt University Center for Teaching. Retrieved 7/20/2018 from
  • Induction for Dental Core Training 2017-2018 NHS Education

    Induction for Dental Core Training 2017-2018 NHS Education

    Available on COPDEND website. DCT Curriculum. NHS Education for Scotland. Minimum of 24 Supervised Learning Events (SLEs) A clinical governance/quality improvement project (e.g. audit) A current personal development plan (PDP) and progress against that PDP.