Bandwidth-based lower bounds on slowdown for efficient emulations of fixed-connection networks
Clyde P. Kruskal, Kevin J. Rappoport · 1994
This paper presents a new method for obtaining lower bounds on the slowdown of efficient emulations between network machines based on their communication bandwidth. The proofs measure the communication complexity of a message pattern by viewing its graph as a network machine and measuring the communication bandwidth β. This approach yields an intuitive lower bound on the time to route a communication pattern represented by multigraph C on a host machine H (with uniform load) as T ≥ Ω (β(C)/β(H)), and thus a lower bound on the slowdown of emulating guest machine G on host H as the ratio of their communication bandwidths.