We propose a new practical technique for the distributed execution-driven simulation of parallel computers. Our simulation methodology allows complete virtualization of the design at all levels and achieves good performance by preserving and exploiting the parallelism of the parallel program being simulated. With our technique it is possible to decouple the simulation of the execution of a parallel application from the estimation of the virtual execution time in which such execution is carried out. Our technique uses minimal overhead to maintain coherent distributed event causality relations by making it possible for the simulated executions to reflect the intrinsic uncertainties of parallel applications being simulated.This approach yields very good performance and has the important side effect of testing the robustness of a design. For the applications we have simulated using our technique, we have observed very good parallel simulation performance and minimal variance in the simulation results, thus demonstrating its practical usefulness. We include a detailed description of our methodology, explain how to apply our ideas to parallelize an existing execution-driven sequential simulator under quite general assumptions, discuss the trade-offs of our methodology, and give preliminary performance measurements of a distributed simulator that uses our technique.