Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks

DOI10.1145/1007352.1007368MaRDI QIDQ3580959zbMATH OpenOpenAlexFDO

Authors Gurmeet Singh Manku, Moni Naor, Udi Wieder

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1007352.1007368

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)

Recommendations

• On the complexity of greedy routing in ring-based peer-to-peer networks
• Degree-optimal routing for P2P systems
• Automata, Languages and Programming
• Close to optimal decentralized routing in long-range contact networks
• Routing networks for distributed hash tables

Cited in

(29)

• The analysis of Kademlia for random IDs
• Distance estimation and object location via rings of neighbors
• Depth of Field and Cautious-Greedy Routing in Social Networks
• \(D^2\)-tree: a new overlay with deterministic bounds
• Neighbor selection and hitting probability in small-world graphs
• Navigable small-world networks with few random bits
• MPC for tech giants (GMPC): enabling Gulliver and the Lilliputians to cooperate amicably
• The expansion and mixing time of skip graphs with applications
• F-Chord: Improved uniform routing on Chord
• The forgiving graph: a distributed data structure for low stretch under adversarial attack
• Shortest-path routing in randomized DHT-based peer-to-peer systems
• Universal augmentation schemes for network navigability
• Greedy routing in small-world networks with power-law degrees
• Close to optimal decentralized routing in long-range contact networks
• Viceroy, a scalable and dynamic emulation of the butterfly
• Optimal routing in a small-world network
• A probabilistic analysis of Kademlia networks
• Low-distortion inference of latent similarities from a multiplex social network
• Could any graph be turned into a small-world?
• D2B: A de Bruijn based content-addressable network
• A model of self-avoiding random walks for searching complex networks
• Greedy routing and the algorithmic small-world phenomenon
• Eclecticism shrinks even small worlds
• Navigation in spatial networks: a survey
• SKY: efficient peer-to-peer networks based on distributed Kautz graphs
• Recovering the long-range links in augmented graphs
• Degree-optimal routing for P2P systems
• Kleinberg's grid unchained
• JumpNet: improving connectivity and robustness in unstructured P2P networks by randomness

This page was built for publication: Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580959)