ABSTRACT

This paper presents a new method for obtaining lower bounds on the slowdown of efficient emulations between network ma- chines 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 8. 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>()), and thus a lower bound on the slowdown of emulating guest machine G on host H as the ratio of their communication bandwidths.