40 %
60 %
Information about stoc04

Published on June 18, 2007

Author: CoolDude26


Know thy Neighbor’s NeighborThe Power of Lookahead in Randomized P2P Networks:  Know thy Neighbor’s Neighbor The Power of Lookahead in Randomized P2P Networks Moni Naor Udi Wieder The Weizmann Institute of Science Gurmeet Manku Stanford The Small World Phenomenaa very brief history:  The Small World Phenomena a very brief history Folklore – People are connected via short chains – The graph of social networks has small diameter. Barabasi: belief may have originated from a story by Frigyes Karinthy, 1929 Quantitative approach initiated by Milgram in the 1960’s - 'The six degrees of separation'. Mathematical modeling: Model a social network by some distribution on graphs. A precursor of P2P – need to locate a resource in a ‘natural’ network based on partial information. Routing in a Small World:  Routing in a Small World Common question: do short paths exist? Algorithmic question: assuming short paths exist. How do people find them? Modeling Small Worlds:  Modeling Small Worlds Kleinberg’s model [2000]: People  points on a two dimensional grid. Grid edges (short range). One long range contact chosen with the Harmonic distribution. probability of (u,v) proportional to 1/d(u,v)2. Naturally generalizes to k long range links (Symphony [MBR03],[ADS02].). Naturally generalizes to any dimension. Captures the intuitive notion that people know people who are close to them. Modeling Small Worlds:  Modeling Small Worlds Small World Percolation: People  points on a two dimensional grid. Grid edges (short range). Each edge appears independently with probability = inverse of its distance squared. Degree of each node . Originates from long range percolation model. Shares structural properties with some popular randomized P2P networks: R-Chord, R-Hypercube, Skip Lists… Routing in Small Worlds:  Routing in Small Worlds Greedy algorithm: move to the node that minimizes the L1 distance to the target. Properties of Greedy:  Properties of Greedy Simple – to understand and to implement. Local – If source and target are close, the path remains within a small area. In some cases – (Hypercube, Chord) – the best we can do. Not optimal with respect to the degree. Can Greedy Routing be shortened? Without compromising the good properties Neighbor of Neighbor (NoN) Routing:  Neighbor of Neighbor (NoN) Routing Each node has a list of its neighbor’s neighbors. The message is routed greedily to the closest neighbor of neighbor (2 hops). Let w1, w2, … wk be the neighbors of current node u For each wi find zi, the closet neighbor to target t Let j be such that zj is the closest to target t Route the message from u via wj to zj Effectively it is Greedy routing on the squared graph. The first hop may not be a greedy choice. Previous incarnations of the approach: Coppersmith, Gamarnik and Sviridenko [2002]: proved an upper bound on the diameter of a small world graph. No routing algorithm Manku, Bawa and Ragahavan [2003]: a heuristic routing algorithm in ‘Symphony’ - a Small-World like P2P network. Summary of Results:  Summary of Results PSW, R-Chord, R-Hypercube are degree optimal w.h.p. Skip Lists – degree optimal on expectation. Kleinberg’s model and P2P variations – improved. Lower bounds for algorithms based on neighbor lists only (Greedy is a special case). Degree Optimal P2P Routing:  Degree Optimal P2P Routing Different routing schemes Viceroy [MNR02]: emulates the butterfly network Constant degree O(log n) hops for routing Constructions emulating De-Bruijn graphs Can achieve any degree/number of hops tradeoff In particular degree O(log n) and O(log n/ log log n) hops Routing is not greedy Recent construction [AM] fixes that. Even if target and source are close in label space message might be routed away No (natural) prefix search Random keys are necessary. Skip – Graphs [AS02],[HDJ+03]:  Skip – Graphs [AS02],[HDJ+03] Each node (resource) has a name. Nodes are arranged on a line sorted by name. Each node chooses a random string of bits. An edge is established if two nodes share a prefix which is not shared by the nodes between them. Allows prefix search. a b c f e d Routing in Skip – Graphs:  Routing in Skip – Graphs Greedy Routing – use longest edge possible. Path length is (log n) w.h.p. The NoN algorithm optimizes over two hops. Skip Graphs – degree optimality:  Call a NoN 2-hop successful if it reduces the distance from d to . Need succesful 2-hops to get to distance 1. From Lemma, this would take in expectation. Skip Graphs – degree optimality d 0 X - # of two hop paths between d and D - the event a message reached the node d. Lemma: Prob Sufficiency of lemma: Skip Graphs – degree optimality:  Ai,j - There exists an edge between i, j. X - # of two hop paths between d and Want to show Prob . Ignore dependence on D. Skip Graphs – degree optimality 0 d Choice of constants Skip Graphs – degree optimality:  0 d i j x y Ai,j - There exists an edge between i, j. X - # of two hop paths between d and Skip Graphs – degree optimality The Cost/Performance of NoN:  The Cost/Performance of NoN Cost of Neighbor of Neighbor lists: Memory: O(log2n) - marginal. Communication: Is it tantamount to squaring the degree? Neighbor lists should be maintained (open connection, pinging, etc.) NoN lists should only be kept up-to-date. Reduce communication by piggybacking updates on top of the maintenance protocol. Lazy updates: Updates occur only when communication load is low – supported by simulations. Networks of size 217 show 30-40% improvement A Case for Randomized Topology:  A Case for Randomized Topology Average diameter of hypercube is . Average diameter of ‘perfect’ skip graph is . Average diameter of Chord is . Conclusion – The randomization of edges reduces the average path lengths. Common design rule – reduce randomization in topology. The long edges are just in the right density, so that NoN finds them without increasing the degree. Other advantages: Security, fault tolerance…. Do People Use the NoN Algorithm?:  Do People Use the NoN Algorithm? Experiment based on email [DRW03] About 25% sent the mail because: The recipient traveled to target’s geographical region. The recipient’s family originates from target’s geographical region. Lower Bounds – A Probing Model:  Lower Bounds – A Probing Model Goal: Find a path between two nodes in an unknown graph. The algorithm may probe a node. If the probing reveals a neighborhood of radius k, then the algorithm is k – local. A lower bound on the number of probes implies a lower bound on the sequential running time of routing. The Greedy algorithm is 1-local. NoN is 2-local. Conclusion: Some extra information is necessary. Greedy algorithm dominates1-local algorithms.:  Greedy algorithm dominates1-local algorithms. Let A be a 1-local algorithm. Denote by the r.v counting the number of probes it takes A (Greedy) to find a path between 0;d. If a probe finds node i, reveal all edges (prefixes) in [d;i]. Only increases . The ‘best chance’ of getting close to 0 is by probing the node closest to 0. 0 d i revealed Lower Bounds on Greedy:  Lower Bounds on Greedy Partition the nodes to balls B0,B1,…,Blog d Define Xi – the indicator of the event : 'Greedy probed a node in Bi' The probe complexity is at least . d 0 B0 B3 B2 B1 Azuma’s inequality: Lower Bounds on Greedy:  Lower Bounds on Greedy Xi depends only on the last ball visited. When a ball is visited – skip to the last node. Assume X0=1,X1=0. The probability the dangling edge would skip over B2 is at most . Conclusions:  Conclusions NoN Greedy seems like an almost free tweak that is a good idea in many settings. Do not be perfect (all the time) – randomization helps. What is more important Prefix search. Easy and ‘natural’ degree optimality. Better understanding of the ‘small world’ phenomena.

Add a comment

Related presentations

Related pages

stoc04 - Ace Recommendation Platform - 1

Lower Bounds for Linear Degeneracy Testing∗Nir AilonDepartment of Computer SciencePrinceton Universitynailon@cs.princeton.eduBernard ChazelleDepartment ...
Read more

stoc04 - Ace Recommendation Platform - 1

Rational Secret Sharing and Multiparty Computation:Extended AbstractJoseph Halpern∗Department of Computer ScienceCornell UniversityIthaca, NY ...
Read more

On the Performance of Greedy Algorithms in Packet Buffering

On the Performance of Greedy Algorithms in Packet Buffering Susanne Albers y Markus Schmidt z Abstract We study a basic buffer management problem that ...
Read more

Geometry and Expansion: A survey of some results Sanjeev ...

Geometry and Expansion: A survey of some results Sanjeev Arora Princeton ( touches upon: S. A., Satish Rao, Umesh Vazirani, STOC04; S. A., Elad Hazan,
Read more

Rational Secret Sharing and Multiparty Computation ...

Rational Secret Sharing and Multiparty Computation: Extended Abstract Joseph Halpern ⁄ Department of Computer Science Cornell University Ithaca, NY 14853
Read more

PowerPoint Presentation - Colorado

Title: PowerPoint Presentation Author: krtko Last modified by: Laszlo Babai Created Date: 6/12/2004 6:36:34 AM Document presentation format: On-screen Show
Read more

Visibly Pushdown Languages - University of Pennsylvania

Visibly Pushdown Languages Rajeev Alur University of Pennsylvania P. Madhusudan University of Illinois, Urbana-Champaign
Read more

Computing Nash Equilibria for Scheduling on Restricted ...

Computing Nash Equilibria for Scheduling on Restricted Parallel Links Martin Gairingy Thomas Luc¨ kingy Marios Mavronicolasz Burkhard Monieny ABSTRACT
Read more

1 x Heritage STOC04 Torre Flex Kit Chrome Shower Riser ...

1 x Heritage STOC04 Torre Flex Kit Chrome Shower Riser, Hose & Shower Head - Polished CHrome Finish - CL009 - New Boxed Stock - Location: Altrincham WA14
Read more

STOC 2004 Local Arrangements - DePaul University

Symposium on Theory of Computing (STOC '04) Dates: Sunday, June 13th, to Tuesday, June 15th, 2004. Venue: Chicago Hilton and Towers. The conference has ...
Read more