Optimal trade-offs between size and slowdown for universal parallel networks

A parallel processor network is called n-universal with slowdown s, if it can simulate each computation of each constant-degree processor network with n processors with slowdown s. We prove the following lower bound trade-off: For each constant-degree n-universal network of size m with slowdown s, m x s=#OMEGA#(n log m) holds. Our trade-off holds for a very general model of simulations. It covers all previously considered models and all known techniques for simulations among networks. For m#>=#n, this improves a previous lower bound by a factor of log n, proved for a weaker simulation model. For m<n, this is the first non-trivial lower bound for this problem. In this case, this lower bound is asymptotically tight. (orig.)SIGLEAvailable from TIB Hannover: RR 6673(36) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDeutsche Forschungsgemeinschaft (DFG), Bonn (Germany); European Union (Euro), Brussels (Belgium)DEGerman