Stephen R. Donaldson, Jonathan M.D. Hill, and David B. Skillicorn
Abstract:
The cost of communication in message-passing systems can only be computed based on a large number of low-level details. Consequently, the only architectural measure they naturally suggest is a first-order one, latency. We show that a second-order property, the standard deviation of the delivery times is also of interest.
Most importantly, the average performance of a large communication system depends not only on the average performance of its components, but also on the standard deviation of these performances. In other words, building a high-performance system requires components that are themselves high-performance, but their performance must also have small variance.
We illustrate this effect using distributions of the BSP g parameter. Lower bounds on the communication performance of large systems can be derived from data measured over single links.