This paper documents the origins and development of the parallel and distributed simulation field, especially as it relates to parallel discrete event simulation (PDES) technology. My focus is on the people and ideas that contributed to the creation and evolution of PDES technology over the past five decades. Much of this paper reviews the research conducted in academia and research laboratories that were the driving forces behind the development of PDES technology as well as subsequent efforts in government and industry to bring the technology to modeling and simulation practitioners. The origins of PDES technology lie in a fundamental technical issue called the synchronization problem. This problem is discussed, as well as the two main solution approaches that were created. The development of these approaches and their evolution to form the time management services of the High Level Architecture (HLA) standard are described, as well as the community of researchers and practitioners that formed in establishing this field. Commercialization efforts are discussed followed by a brief discussion of areas requiring further research. The importance of the Society for Modeling and Simulation International (SCS) and its flagship journal, Simulation, in the development of the field are discussed. Throughout this discussion, I provide my personal observations and take away lessons concerning the development of the field.
ThorpeJ. Trends in modeling, simulation, & gaming: personal observations about the past 30 years and speculation about the next 10. In: Proceedings of the interservice/industry training, simulation and education conference (Paper No. IF1001), Orlando, FL, 29 November–2 December 2010.
2.
GormanPF. Learning to learn: reminiscences and anticipation. In: Proceedings of the interservice/industry training, simulation and education conference, Orlando, FL, 28 November–3 December 2011.
3.
ShiflettJE. Observations on the development and implementation of distributed simulation. In: Proceedings of the interservice/industry training, simulation and education conference (Paper No. IF1301), Orlando, FL, 2–5 December 2013.
4.
MillerD. SIMNET and beyond: a history of the development of distributed simulation. In: Proceedings of the interservice/industry training, simulation and education conference, Orlando, FL, 30 November–4 December 2015.
5.
DonovanT. Replay: the history of video games. East Sussex: Yellow Ant; 2010.
6.
FujimotoRMBagrodiaRBryantRE. et alParallel discrete event simulation: the making of a field. In: Winter simulation conference, Las Vegas, NV, 3–6 December 2017.
7.
JeffersonDFujimotoRM.A brief history of time warp. In: JeffersonDFujimotoR (eds) Advances in modeling and simulation. Cham: Springer, 2017, pp. 97–134.
8.
FujimotoRM. Parallel discrete event simulation: past, present, and future. In: Proceedings of the interservice/industry training, simulation, and education conference (I/ITSEC), Orlando, FL, 2–6 December 2019.
FujimotoRM. Parallel and distributed simulation. In: Winter simulation conference, Huntington Beach, CA, 6–9 December 2015.
11.
ChandyKMMisraJ. Distributed simulation: a case study in design and verification of distributed programs. IEEE Trans Softw Eng1979; SE-5: 440–452.
12.
BryantRE. Simulation of packet communication architecture computer systems (MIT-LCS-TR-188). MS Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1977.
13.
PeacockJKWongJWManningEG. Distributed simulation using a network of processors. Comput Netw1979; 3: 44–56.
14.
ChandyKMisraJ. Asynchronous distributed simulation via a sequence of parallel computations. Commun ACM1981; 24: 198–206.
15.
ChandyKMShermanR. Space, time, and simulation. SCS Simul Ser1989; 21: 53–57.
16.
ChandyKMShermanR. The conditional event approach to distributed simulation. Proceedings of the SCS Multiconference on Distributed Simulation, Society for Computer Simulation1989; 21: 93–99.
BauerHSporrerCKrodelTH. On distributed logic simulation using time warp. In: HalaasADenyerPB eds. VLSI ’91 (IFIP TC 10/WG 10.5). Edinburgh: North Holland, 1991, pp. 127–136.
19.
CarothersCPerumallaKSFujimotoRM. Efficient optimistic parallel simulations using reverse computation. ACM Trans Model Comput Simul1999; 9: 224–253.
20.
JeffersonDSowizralH. Fast concurrent simulation using the time warp method, Part I: local control. Santa Monica, CA: The RAND Corporation, 1982.
21.
JeffersonD. Virtual time. In: International conference on parallel processing, Columbus, Ohio, 23–26August. IEEE Computer Society Press, 1983, pp. 384–394.
22.
ReedDAMalonyADMcCredieBD. Parallel discrete event simulation using shared memory. IEEE Trans Softw Eng1988; 14: 541–553.
23.
FujimotoRM. Performance measurement of distributed simulation strategies. Distrib Simul 1988; 19: 14–20.
FujimotoRM. Time warp on a shared memory multiprocessor. Trans Soc Comput Simul1989; 6: 211–239.
26.
DasSFujimotoRMPanesarK. et alGTW: a time warp system for shared memory multiprocessors. In: Proceedings of the 1994 winter simulation conference, Lake Buena Vista, FL, 11–14 December 1994, pp. 1332–1339. New York: IEEE.
27.
CarothersCBauerDPearceS. ROSS: a high-performance, low memory, modular time warp system. J Parallel Distrib Comput2002; 62: 1648–1669.
28.
JeffersonDRBeckmanBWielandF. et alTime warp operating systems. In: 11th symposium on operating systems principles, Austin, TX, 8–11 November 1987, pp. 77–93. New York: ACM.
29.
WielandFHawleyLFeinbergA. et alDistributed combat simulation and time warp: the model and its performance. In: Proceedings of the SCS multiconference on distributed simulation, SCS simulation series, San Diego, CA, 4–6January. San Diego, CA: Society for Computer Simulation, 1989, pp. 14–20.
30.
WielandF. Practical parallel simulation applied to aviation modeling. In: Proceedings of the 15th workshop on parallel and distributed simulation, Lake Arrowehead, CA, 15–18 May 2001, pp. 109–116. New York: IEEE.
31.
JeffersonDR. Virtual time II: storage management in distributed simulation. Proceedings of the ninth annual ACM symposium on principles of distributed computing, Quebec City Quebec Canada, 22–24August. New York: Association for Computing Machinery, 1990, pp. 75–89.
32.
VulovGHouCVuducR. et alThe backstroke framework for source level reverse computation applied to parallel discrete event simulation. In: Winter simulation conference, Phoenix, AZ, 11–14 December 2011.
33.
BarnesPDCarothersCDJeffersonDR. et alWarp speed: executing time warp on 1,966,080 cores. Principles of Advanced Discrete Simulation, Montreal, QC, Canada, 19–22 May 2013, pp. 327–336. New York: ACM.
34.
FujimotoRMHybinetteM. Computing global virtual time in shared memory multiprocessors. ACM Trans Model Comput Simul1997; 7: 425–446.
35.
LomowGDasSFujimotoRM. Mechanisms for user invoked retraction of events in time warp. ACM Trans Model Comput Simul1991; 1: 219–243.
36.
GafniA. Rollback mechanisms for optimistic distributed simulation systems. In: UngerBJeersonD (eds) Proceedings of the SCS multiconference on distributed simulation. San Diego, CA: Society for Computer Simulation, 1988, pp. 61–67.
37.
WestD. Optimizing time warp: lazy rollback and lazy re-evaluation. MS Thesis, University of Calgary, Calgary, AB, Canada, 1988.
38.
LinY-BPreissBR. Optimal memory management for time warp parallel simulation. ACM Trans Model Comput Simul1991; 1: 283–307.
39.
LinY-BPreissBRLoucksWM. et alSelecting the checkpoint interval in time warp simulations. In: Proceedings of the 7th workshop on parallel and distributed simulation, San Diego, CA, 16–19May. San Diego, CA: Society for Computer Simulation, 1993, pp. 3–10.
40.
RonngrenRLiljenstamMAyaniR. et alTransparent incremental state saving in time warp parallel discrete event simulation. In: Workshop on parallel and distributed simulation, Philadelphia, PA, 22–24 May 1996, pp. 70–77. New York: IEEE Computer Society.
41.
WestDPanesarK. Automatic incremental state saving. In: Workshop on parallel and distributed simulation, Philadelphia, PA, 22–24 May 1996, pp. 78–85. New York: IEEE Computer Society.
42.
FleischmannJWilseyPA. Comparative analysis of periodic state saving techniques in time warp simulators. In: Proceedings of the 9th workshop on parallel and distributed simulation, Lake Placid, NY, 14–16 June 1995, pp. 50–58. New York: IEEE.
43.
FujimotoRMTsaiJJGopalakrishnanG. Design and evaluation of the roll back chip: special purpose hardware for time warp. IEEE Trans Comput1992; C-41: 68–82.
44.
FujimotoRM. The virtual time machine. In: International symposium on parallel algorithms and architectures, Santa Fe, New Mexico, 18–21June1989. New York: Association for Computing Machinery, 1989, pp. 199–208.
45.
SamadiB. Distributed simulation, algorithms and performance analysis. Los Angeles, CA: University of California, Los Angeles, 1985.
46.
MatternF. Efficient algorithms for distributed snapshots and global virtual time approximation. J Parallel Distrib Comput1993; 18: 423–434.
47.
BuzzellCAFujimotoRMRobbMJ. Modular VME rollback hardware for time warp. In: 1990 distributed simulation conference, San Diego, CA, 17–19January1990. San Diego CA: Society for Computer Simulation, pp. 153–156.
48.
BerryOJeffersonD. Critical path analysis of distributed simulation. In: Society for computer simulation conference on distributed simulation, San Diego, CA, 24–26 January 1985.
49.
JeffersonD. Virtual time. ACM Trans Program Lang Syst1985; 7: 404–425.
50.
FujimotoRMHunterMSirichokeJ. et alAd hoc distributed simulations. In: Principles of advanced and distributed simulation, San Diego, CA, 12–15 June 2007.
51.
HuangY-LAlexopoulosCHunterM. et alAd hoc distributed simulation methodology for open queueing networks. Trans Soc Model Simul Int2012; 88: 784–800.
52.
TangYFujimotoRMPerumallaK. et alOptimistic parallel simulations of physical systems using reverse computation. Trans Soc Model Simul Int2006; 82: 61–73.
53.
SchordanMJeffersonDBarnesPJr. et alReverse code generation for parallel discrete event simulation. In: 7th conference on reversible computation, Grenoble, France, 16–17 July 2015.
54.
SchordanMOppelstrupTJeffersonD. et alAutomatic generation of reversible C++ code and its performance in a scalable kinetic Monte-Carlo application. In: SIGSIM PADS (principles of advanced discrete simulation), Banff, AB, Canada, 16–18 May 2016.
55.
FerenciSFujimotoRAmmarMH. et alUpdateable simulation of communication networks. In: 16th workshop on parallel and distributed simulation, Washington, DC, 12–15 May 2002.
56.
HybinetteMFujimotoRM. Cloning parallel simulations. ACM Trans Model Comput Simul2001; 11: 378–407.
57.
LavenbergSMuntzRSamadiB. Performance analysis of a rollback method for distributed simulation. In: Performance ‘83: proceedings of the 9th international symposium on computer performance modelling, measurement and Evaluation, May 1983, pp. 117–132. New York: North Holland Publishing.
58.
GuptaAAkyildizIFFujimotoRM. Performance analysis of time warp with multiple homogeneous processors. IEEE Trans Softw Eng1991; 17: 1013–1027.
59.
AkyildizIFChenLDasSR. et alThe effect of memory capacity on time warp performance. J Parallel Distrib Comput1993; 18: 411–422.
60.
NicolDM. The cost of conservative synchronization in parallel discrete event simulations. J ACM1993; 40: 304–333.
61.
DickensPMNicolDMReynoldsJPF. et alAnalysis of bounded time warp and comparison with YAWNS. ACM Trans Model Simul Comput1996; 6: 297–320.
62.
DasSRFujimotoRM. Adaptive memory management and optimism control in time warp. ACM Trans Model Comput Simul1997; 7: 239–271.
63.
DasSRFujimotoRM. An empirical evaluation of performance-memory tradeoffs in time warp. IEEE Trans Parallel Distrib Syst1997; 8: 210–224.
64.
CarothersCDFujimotoRM. Efficient execution of time warp programs on heterogeneous, NOW platforms. IEEE Trans Parallel Distrib Syst2000; 11: 299–317.
65.
ParkAFujimotoRM. A scalable framework for parallel discrete event simulations on desktop grids. In: Proceedings of the 8th IEEE/ACM international conference on grid computing, Austin, TX, 19–21 September 2007.
66.
ParkAFujimotoRM. Efficient master/worker parallel discrete event simulation on metacomputing systems. IEEE Trans Parallel Distrib Syst2012; 23: 873–880.
67.
ParkAFujimotoRM. Optimistic parallel simulation over public resource-computing infrastructures and desktop grids. In: Proceedings of the workshop on distributed simulations and real-time applications, Vancouver, BC, Canada, 27–29 October 2008.
68.
MalikAWParkAJFujimotoRM. An optimistic parallel simulation protocol for cloud computing environments. SCS Model Simul Mag Soc Model Simul Int2010; 1: 61.
69.
ReynoldsPFJr. A spectrum of options for parallel simulation. In: Proceedings of the winter simulation conference, San Diego, CA, 12–14 December 1988.
GroseljBTropperC. The time of next event algorithm. Soc Comput Simul1988; 19: 25–29.
72.
SokolLMBriscoeDP. MTW: a strategy for scheduling discrete simulation events for concurrent execution. In: Proceedings of the SCS multiconference on distributed simulation, San Diego, CA, 3–5 February 1988.
73.
DickensPMReynoldsJPF. SRADS with local rollback. Distrib Simul1990; 22: 161–164.
74.
MadisettiVWalrandJMesserschmittD. WOLF: a rollback algorithm for optimistic distributed simulation systems. In: Proceedings of the 1988 winter simulation conference, San Diego, CA, 1988, pp. 296–305. New York: IEEE.
75.
SteinmanJ. Breathing time warp. In: Proceedings of the 7th workshop on parallel and distributed simulation, San Diego, CA, 16–19May. San Diego, CA: Society for Computer Simulation, 1993, pp. 109–118.
76.
BallDHoytS. The adaptive time warp concurrency control algorithm. Distrib Simul1990; 22: 174–177.
77.
FerschaA. Probabilistic adaptive direct optimism control in time warp. In: Proceedings of the 9th workshop on parallel and distributed simulation, Lake Placid, NY, 14–16 June 1995, pp. 120–129. New York: IEEE.
78.
LubachevskyBDShwartzAWeissA. Rollback sometimes works...if filtered. In: Proceedings of the 1989 winter simulation conference, Washington, DC, 4–6 December 1989.
79.
ChowACZeiglerB. Parallel DEVS: a parallel, hierarchical, modular modeling formalism. In: TewJDManivannanSSadowskiDA. et al (eds) Proceedings of the winter simulation conference. New York: IEEE, 1994, pp. 716–722.
80.
NicolDMLiuJ. Composite synchronization for parallel discrete event simulation. IEEE Trans Parallel Distrib Syst2002; 13: 433–446.
81.
ArvindKSmartC. Hierarchical parallel discrete event simulation in composite Elsa. In: Proceedings of the 6th workshop on parallel and distributed simulation, Newport Beach, CA, 20–22 January 1992. San Diego, CA: Society for Computer Simulation, pp. 147–158.
82.
RajaeiHAyaniRThorelliLE. The local time warp approach to parallel simulation. In: Proceedings of the 7th workshop on parallel and distributed simulation, San Diego, CA, 16–19 May 1993.
83.
JhaVBagrodiaR. A unified framework for conservative and optimistic distributed simulation. SIGSIM Simul Dig1994; 24: 12–19.
84.
AyaniR. A parallel simulation scheme based on the distance between objects. Soc Comput Simul1989; 21:113–118.
85.
RonngrenRAyaniR. Adaptive checkpointing in time warp. In: Proceedings of the 8th workshop on parallel and distributed simulation, Edinburgh, Scotland UK, 6–8July1994. San Diego, CA: Society for Computer Simulation, pp. 110–117.
86.
CaiWTurnerS. An algorithm for distributed discrete—event simulation—the “carrier mull message” approach. Distrib Simul1990; 22: 3–8.
87.
SantoroAQuagliaF. Transparent optimistic synchronization in the high-level architecture via time-management conversion. ACM Trans Model Comput Simul2012; 22: 21:1–21:26.
88.
NicolDMLiuX. The dark side of risk (what your mother never told you about time warp). In: Proceedings of the 11th workshop on parallel and distributed simulation, Lockenhaus, Austria, 10–13 June 1997, pp. 188–195. New York: IEEE.
89.
PresleyMReiherPBellenotS. A time warp implementation of sharks world. In: Proceedings of the winter simulation conference, New Orleans, LA, 9–12 December 1990, pp. 199–203. New York: IEEE.
90.
BagrodiaRLLiaoWT. Parallel simulation of the sharks world problem. In: Proceedings of the winter simulation conference, New Orleans, LA, 9–12 December 1990.
91.
NicolDRiffeSE. A “conservative” approach to parallelizing the sharks world simulation. In: Proceedings of the winter simulation conference, New Orleans, LA, 9–12 December 1990, pp. 186–190. New York: IEEE.
92.
FujimotoRM. Parallel discrete event simulation: will the field survive?ORSA J Comput1993; 5: 213–230.
93.
WilsonALWeatherlyRM. The aggregate level simulation protocol: an evolving system. In: Proceedings of the 1994 winter simulation conference, Lake Buena Vista, FL, 11–14 December 1994, pp. 781–787. New York: IEEE.
94.
FujimotoRM. Time management in the high level architecture. Simulation1998; 71: 388–400.
95.
FujimotoRMHoareP. HLA RTI performance in high speed LAN environments. In: Proceedings of the fall simulation interoperability workshop, Orlando, FL, 18–18September1998.
96.
FallK. Network emulation in the VINT/NS simulator. In: Proceedings of the IEEE international symposium on computers and communications, Red Sea, Egypt, 6–8 July 1999, pp. 244–250. New York: IEEE.
97.
RileyGAmmarMFujimotoRM. et alA federated approach to distributed network simulation. ACM Trans Model Comput Simul2004; 14: 116–148.
98.
FujimotoRMPerumallaKSParkA. et alLarge-scale network simulation: how big? How fast? In: Proceedings of the modeling, analysis and simulation of computer and telecommunication systems, Orlando, FL, 12–15 October 2003.
99.
PelkeyJRileyG. Distributed simulation with MPI in NS-3. In: Proceedings of the international ICST conference on simulation tools and techniques, Barcelona, 21–25 March 2011, pp. 410–414. Brussels: Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering.
100.
FerenciSPerumallaKFujimotoR. An approach to federating parallel simulators. In: Proceedings of the 14th workshop on parallel and distributed simulation, Bologne, 28–31 May 2000.
101.
BaeznerDLomowGUngerBW. Sim++: the transition to distributed simulation. In: Proceedings of the SCS conference on distributed simulation, San Diego, CA, 17–19January1990. San Diego CA: Society for Computer Simulation, pp. 211–218.
102.
GomesFClearyJCovingtonA. et alSimkit: a high performance logical process simulation class library in C++. In: LilegdonWGoldsmanDAlexopoulosC. et al (eds) Proceedings of the winter simulation conference. New York: Institute of Electrical and Electronics Engineers, 1995, pp. 706–713.
103.
BagrodiaRLiaoWT. Maisie: a language for the design of efficient discrete-event simulations. IEEE Trans Softw Eng1994; 20: 225–238.
104.
ZengXBagrodiaRGerlaM. GloMoSim: a library for parallel simulation of large-scale wireless networks. In: Proceedings of the workshop on parallel and distributed simulation, Banff, AB, Canada, 29 May 1998.
105.
ZhouJJiZBagrodiaR. TWINE: a hybrid emulation testbed for wireless networks and applications. In: Proceedings of the IEEE international conference on computer communications, Barcelona, 23–29 April 2006.
106.
StoffersMBettermannRGrossJ. et alEnabling distributed simulation of OMNeT++ INET models. In: Proceedings of the OMNeT++ community summit, Hamburg, 2September2014.
107.
SteinmanJ. SPEEDES: synchronous parallel environment for emulation and discrete event simulation. Distrib Simul1991; 23: 95–103.
108.
ZhengrongJZhouJTakaiM. et alImproving scalability of wireless network simulation with bounded inaccuracies. ACM Trans Model Comput Simul2006; 16: 329–356.
109.
PientaRFujimotoRM. On the parallel simulation of scale-free networks. In: Proceedings of the principles of advanced and discrete simulation, Montreal, Quebec Canada, 19–22May2013. New York: Association for Computing Machinery.
110.
PerumallaKSBrandonGASrikanthBY. et alGPU-based real-time execution of vehicular mobility models in large-scale road network scenarios. In: Proceedings of the principles of advanced and distributed simulation, Lake Placid, NY, 22–25 June 2009, pp. 95–103. New York: IEEE.
111.
ParkHFishwickP. An analysis of queuing network simulation using GPU-based hardware acceleration. ACM Trans Model Comput Simul2011; 21: 1–22.
112.
XuYTanGLiX. et alMesoscopic traffic simulation on CPU/GPU. In: Proceedings of the principles of advanced discrete simulation, Denver, CO, 18–21May2014. New York: Association for Computing Machinery, pp. 39–49.
113.
FujimotoRMLuncefordDPageE. et alGrand challenges in modeling and simulation (Seminar No. 02351). Technical report no. 350, 28–30August2002. Leibniz-Zentrum fur Informatik: Schloss Dagstuhl.
114.
DaremaF. Dynamic data driven applications systems: a new paradigm for application simulations and measurements. In: BubakMvan AlbadaGDSlootPMA. et al (eds) Proceedings of the international conference on computational science. Kraków: Springer, 2004, pp. 662–669.
115.
BlaschERavelaSAvedA. et alHandbook of dynamic data driven application systems. Cham: Springer International Publishing, 2018.
116.
FujimotoRM. Power consumption in modeling and simulation. J Simul2020; 14: 157–168.
