Almost linear speed-up of distributed discrete event simulations

A distributed simulation algorithm is presented which explores the topology of the simulated system using precomputed minimum propagation delays between subsystems. The algorithm also uses opaque periods which are the delays caused by the nonpreemptive states these subsystems can enter. The algorithm achieves Θ(N/log N) speed-up when run on an appropriate physically realizable N-processor parallel computer. No other algorithm for distributed discrete event simulation has been theoretically shown to achieve this level of efficiency. Experiments show speed-ups of greater than 20 on 25 processors of a shared memory MIMD computer and greater than 1900 on 2¹⁴ processors of a SIMD computer