Routing complexity of faulty networks

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

Itai Benjamini, Omer Angel, Udi Wieder, Eran Ofek

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

hypercube; percolation; phase transition; random graphs; lower bound; fault tolerance; routing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C80: Random graphs (graph-theoretic aspects)

90B18: Communication networks in operations research

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68M14: Distributed systems

68M15: Reliability, testing and fault tolerance of networks and computer systems

68M12: Network protocols

Uses Software

• Chord