Slide Number 1AcknowledgementAdministrative Administrative Administrative Administrative Plan for TodayPeer pointers (1): successorsPeer pointers (2): finger tables (Scalable Key Location)Mapping FilesSearchSearchSearchAnalysisAnalysis (contd.)Analysis (contd.)Stabilization ProtocolSearch under peer failuresSearch under peer failuresSearch under peer failuresSearch under peer failures (2)Search under peer failures (2)Need to deal with dynamic changesNew peers joiningNew peers joining (2)New peers joining (3)Stabilization ProtocolExperimental ResultsLookupsDiscussionDiscussion (2)Discussion (3)SummaryReview for Midterm Midterm TopicsMidterm TopicsMidterm TopicsMidterm TopicsMidterm TopicsLecture 14Peer-to-Peer systems (Part III) and Midterm Review Session CS 425/ECE 428/CSE 424Distributed Systems(Fall 2009)Acknowledgement• The slides during this semester are based on ideas and material from the following sources: – Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. – Slides from Professor S. Gosh’s course at University o Iowa.Administrative • MP1 scores posted•HW2 solutions postedAdministrative • MP2 posted October 5, 2009, on the course website, – Deadline November 6 (Friday)– Demonstrations , 4-6pm, 11/6/2009 – You will need to lease one Android/Google Developers Phone per person from the CS department (see lease instructions)!!– Start early on this MP2 – Update groups as soon as possible and let TA know by email so that she can work with TSG to update group svn – Tutorial for MP2 planned for October 28 evening if students send questions to TA by October 25. Send requests what you would like to hear in the tutorial. – During October 15-25, Thadpong Pongthawornkamol ([email protected]) will held office hours and respond to MP2 questions for Ying Huang (Ying is going to the IEEE MASS 2009 conference in China)Administrative • MP3 proposal instructions – You will need to submit a proposal for MP3 on top of your MP2 before you start MP3 on November 9, 2009– Exact Instructions for MP3 proposal format will be posted October 9, 2009 – Deadline for MP3 proposal: October 25, 2009, email proposal to TA– At least one representative of each group meets with instructor or TA during October 26-28 during their office hours ) watch for extended office hours during these days.• Instructor office hours: October 28 times 8:30-10amAdministrative • To get Google Developers Phone, you need a Lease Form – You must pick up a lease form from the instructor during October 6-9 (either in the class or during office hours) since the lease form must be signed by the instructor. – Fill out the lease form; bring the lease form to Rick van Hook/Paula Welch and pick up the phone from 1330 SC• Lease Phones: phones will be ready to pick up starting October 20, 9-4pm from room 1330 SC (purchasing , receiving and inventory control office)• Return Phones: phones need to be returned during December 14-18, 9-4pm in 1330 SCPlan for Today• Chord • Review material for midtermPeer pointers (1): successorsN800Say m=7N32N45N112N96N16(similarly predecessors)Each physical node maintains a successor pointerSHA-1(140.45.3.12, 1245) = 42 (0101010)42 stored in the successor N45Logical node 42Peer pointers (2): finger tables(Scalable Key Location)N8080 + 2080 + 2180 + 2280 + 2380 + 2480 + 2580 + 260Each nodemaintainsa finger tableN32N45ith entry at peer with id n is first peer with id >= )2(mod2min +N112N96N16i ft[i]0 961 962 963 964 965 1126 16Finger Table at N80Mapping FilesN800Say m=7N32N45N112N96N16File cnn.com/index.html with key K42 stored hereSearchSay m=7File cnn.com/index.html with key K42 stored hereWho has cnn.com/index.html?(hashes to K42)N800N32N45N112N96N160 321 322 323 324 325 806 800 451 452 453 454 805 806 96i ft[i]0 961 962 963 964 965 1126 16SearchN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereAt node n, send query for key k to largest successor/finger entry < k (all modulo m) if none exist, send query to successor(n)N112N96N16Who has cnn.com/index.html?(hashes to K42)i ft[i]0 961 962 963 964 965 1126 16SearchN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereAll “arrows” are RPCsN112N96N16Who has cnn.com/index.html?(hashes to K42)At node n, send query for key k to largest successor/finger entry < k (all mod m)if none exist, send query to successor(n)(lookup in finger table)(lookup in finger table)N45 > K42, henceTake successori ft[i]0 961 962 963 964 965 1126 1616 < 4232 < 4245 > 42AnalysisSearch takes O(log(N)) timeProof – (intuition): at each step, distance between query and peer-with-file reduces by a factor of at least 2 (why?)Takes at most m steps: is at most a constant multiplicative factor above N, lookup is O(log(N))– (intuition): after log(N) forwardings, distance to key is at most (why?)• Number of node identifiers in a range of is O(log(N)) with high probability• So using successors in that range will be okNm/2Nm/2m2HereNext hopKeyAnalysis (contd.)• O(log(N)) search time holds for file insertions too (in general for routing to any key)– “Routing” can thus be used as a building block for other applications than file sharing [can you name one?]• O(log(N)) time true only if finger and successor entries correct•When might these entries be wrong?Analysis (contd.)• O(log(N)) search time holds for file insertions too (in general for routing to any key)– “Routing” can thus be used as a building block for other applications than file sharing [can you name one?]• O(log(N)) time true only if finger and successor entries correct• When might these entries be wrong?– When you have failuresStabilization Protocol• Maintaining finger tables only is expensivein case of dynamic joint and leave nodes• Chord therefore separates correctness from performance goals via stabilization protocols• Basic stabilization protocol – Keep successor’s pointers correct!– Then use them to correct finger tablesSearch under peer failuresN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereXXXLookup fails (N16 does not know N45)N112N96N16Who has cnn.com/index.html?(hashes to K42)0 321 322 323 324 325 806 80Search under peer failuresN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereXOne solution: maintain r multiple successor entriesin case of failure, use
View Full Document
Unlocking...