Routing complexity of faulty networks

DOI10.1145/1073814.1073854zbMath1314.68150arXivmath/0407185OpenAlexW2142164915MaRDI QIDQ5177243

Eran Ofek, Udi Wieder, Itai Benjamini, Omer Angel

Publication date: 10 March 2015

Published in: Random Structures & Algorithms, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0407185

zbMATH Keywords

hypercubepercolationphase transitionrandom graphslower boundfault tolerancerouting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network protocols (68M12)

Related Items

Finding paths in sparse random graphs requires many queries, Upper bounds on the connection probability for 2-D meshes and tori, A phase transition for the metric distortion of percolation on the hypercube

Uses Software

• Chord

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the fault tolerance of the butterfly
• Probability on Trees and Networks
• The small-world phenomenon
• Know thy neighbor's neighbor
• Percolation
• Multi-scale self-simulation
• Scalable and dynamic quorum systems
• Distributed Computing