Modeling Parallel Bandwidth: Local vs. Global Restrictions

Recently there has been an increasing interest in models of parallel computation that account for the bandwidth limitations in communication networks. Some models (e. g., BSP and LOGP) account for bandwidth limitations using a per-processor parameter g> 1, such that each processor can send/receive at most h messages in g. h time. Other models (e.g., PRAM(m)) account for bandwidth limit ations as an aggregate parameter m < p, such that the p processors can send at most m messages in total at each step. This paper provides the first detailed study of the algorithmic implications of modeling parallel bandwidth as a per-processor (local) limitation versus an aggregate (global) limitation. We consider a number of basic problems such as broadcasting, parity, summation and sorting