Parallel simulation by multi-instruction,longest-path algorithms

This paper presents several basic algorithms for the parallel simulation of G/G/1 queueing systems and certain networks of such systems. The coverage includes systems subject to manufacturing or communication blocking, or to loss of customer due to capacity constraints. The key idea is that the customer departure times are represented by longest-path distance in directed graphs instead of by the usual recursive equations. This representation leads to scalable algorithms with a high degree of parallelism that can be implemented on either MIMD or SIMD parallel computers. This revised version was published online in June 2006 with corrections to the Cover Date.