{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T06:43:47Z","timestamp":1771656227176,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            Algorithms for synchronization of parallel discrete event simulation have historically been divided between\n            <jats:italic>conservative<\/jats:italic>\n            methods that require lookahead but not rollback, and\n            <jats:italic>optimistic<\/jats:italic>\n            methods that require rollback but not lookahead. In this paper we present a new approach in the form of a framework called\n            <jats:bold>\n              <jats:italic>Unified Virtual Time<\/jats:italic>\n              (UVT)\n            <\/jats:bold>\n            that unifies the two approaches, combining the advantages of both within a single synchronization theory. Whenever timely lookahead information is available, a\n            <jats:bold>logical process (LP)<\/jats:bold>\n            executes conservatively using an\n            <jats:italic>irreversible<\/jats:italic>\n            event handler. When lookahead information is not available the LP does not block, as it would in a classical conservative execution, but instead executes optimistically using a\n            <jats:italic>reversible<\/jats:italic>\n            event handler. The switch from conservative to optimistic synchronization and back is decided on an event-by-event basis by the simulator, transparently to the model code. UVT treats conservative synchronization algorithms as optional accelerators for an underlying optimistic synchronization algorithm, enabling the speed of conservative execution whenever it is applicable, but otherwise falling back on the generality of optimistic execution.\n          <\/jats:p>\n          <jats:p>We describe UVT in a novel way, based on fundamental invariants, monotonicity requirements, and synchronization rules. UVT permits zero-delay messages and pays careful attention to tie-handling using superposition. We prove that under fairly general conditions a UVT simulation always makes progress in virtual time.<\/jats:p>\n          <jats:p>This is Part 1 of a trio of papers describing the UVT framework for PDES, mixing conservative and optimistic synchronization and integrating throttling control.<\/jats:p>","DOI":"10.1145\/3505248","type":"journal-article","created":{"date-parts":[[2022,9,23]],"date-time":"2022-09-23T11:54:44Z","timestamp":1663934084000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Virtual Time III, Part 1: Unified Virtual Time Synchronization for Parallel Discrete Event Simulation"],"prefix":"10.1145","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3991-6038","authenticated-orcid":false,"given":"David R.","family":"Jefferson","sequence":"first","affiliation":[{"name":"Lawrence Livermore National Laboratory, Livermore, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0326-5819","authenticated-orcid":false,"suffix":"Jr","given":"Peter","family":"Barnes","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory, Livermore, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/130611.130614"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"e_1_3_3_4_1","article-title":"Critical path analysis of distributed simulation","author":"Berry O.","year":"1985","unstructured":"O. Berry and D. Jefferson. 1985. Critical path analysis of distributed simulation. In Proceedings of the 1985 SCS Conference on Distributed Simulation, San Diego, CA.","journal-title":"Proceedings of the 1985 SCS Conference on Distributed Simulation,"},{"key":"e_1_3_3_5_1","author":"Berry O.","year":"1986","unstructured":"O. Berry. 1986. Performance Evaluation of the Time Warp Distributed Simulation Mechanism. PhD dissertation, Dept, of Computer Science, University of Southern California, Los Angeles, CA.","journal-title":"Performance Evaluation of the Time Warp Distributed Simulation Mechanism"},{"key":"e_1_3_3_6_1","author":"Bryant R. E.","year":"1977","unstructured":"R. E. Bryant. 1977. Simulation of Packet Communication Architecture Computer Systems. M.I.T. MS thesis, MIT\/LCS\/TR-188.","journal-title":"Simulation of Packet Communication Architecture Computer Systems"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/347823.347828"},{"key":"e_1_3_3_8_1","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1109\/WSC.2010.5679119","volume-title":"Proc. of the 2010 Winter Simulation Conference","author":"Carothers C. D.","year":"2010","unstructured":"C. D. Carothers and K. S. Perumalla. 2010. On deciding between conservative and optimistic approaches on massively parallel platforms. In Proc. of the 2010 Winter Simulation Conference, Edited by B. Johansson, S. Jain, J. Montoya-Torres, J. Hugan, and E. Y\u00fccesan, 678\u2013687."},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.230182"},{"key":"e_1_3_3_10_1","article-title":"Space-time and simulation. Distributed Simulation 1989, the Society for Computer Simulation","author":"Chandy K. M.","year":"1989","unstructured":"K. M. Chandy and R. Sherman. 1989. Space-time and simulation. Distributed Simulation 1989, the Society for Computer Simulation. University of Southern California Information Sciences Institute ISI Reprint Series #238.","journal-title":"University of Southern California Information Sciences Institute ISI Reprint Series #238"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077583"},{"key":"e_1_3_3_12_1","first-page":"36","article-title":"FNCS: A framework for power system and communication networks co-simulation","author":"Ciraci S.","year":"2014","unstructured":"S. Ciraci, J. Daily, J. Fuller, A. Fisher, L. Marinovici, and K. Agarwal. 2014. FNCS: A framework for power system and communication networks co-simulation. In Proceedings of the Symposium on Theory of Modeling & Simulation - DEVS Integrative (DEVS'14). Society for Computer Simulation International, San Diego, CA, USA, Article 36 (2014), 8.","journal-title":"Proceedings of the Symposium on Theory of Modeling & Simulation - DEVS Integrative (DEVS'14)"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/PADS.1995.404317"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59936-6_2"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/268403.268404"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1177\/003754979807100604"},{"key":"e_1_3_3_17_1","volume-title":"Parallel and Distributed Simulation Systems","author":"Fujimoto R. M.","year":"2000","unstructured":"R. M. Fujimoto. 2000. Parallel and Distributed Simulation Systems. New York: John Wiley & Sons, Wiley InterScience."},{"key":"e_1_3_3_18_1","author":"Gomes F. A. F. B.","year":"1996","unstructured":"F. A. F. B. Gomes. 1996. Optimizing Incremental State Saving and Restoration. PhD Dissertation, University of Calgary, Calgary, Alberta (1996).","journal-title":"Optimizing Incremental State Saving and Restoration"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359585"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/DISTRA.2017.8167663"},{"key":"e_1_3_3_21_1","article-title":"Fast concurrent simulation using the time warp mechanism","author":"Jefferson D. R.","year":"1982","unstructured":"D. R. Jefferson and H. Sowizral. 1982. Fast concurrent simulation using the time warp mechanism. Part I: Local Control\u201d, Rand Note N-1906-AF, The Rand Corporation, Santa Monica, CA.","journal-title":"Part I: Local Control\u201d, Rand Note N-1906-AF, The Rand Corporation"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3916.3988"},{"key":"e_1_3_3_23_1","first-page":"77","article-title":"Distributed simulation and the time warp operating system","author":"Jefferson D. R.","year":"1987","unstructured":"D. R. Jefferson, B. Beckman, F. Wieland, L. Blume, M. DiLoreto, P. Hontalas, P. Laroche, K. Sturdevant, J. Tupman, V. Warren, J. Wedel, H. Younger, and S. Bellenot. 1987. Distributed simulation and the time warp operating system. Proceedings of the ACM Symposium on Operating System Principles (SOSP), 77\u201393.","journal-title":"Proceedings of the ACM Symposium on Operating System Principles (SOSP)"},{"key":"e_1_3_3_24_1","article-title":"Virtual Time II: Storage management in conservative and optimistic systems","author":"Jefferson D. R.","year":"1990","unstructured":"D. R. Jefferson. 1990. Virtual Time II: Storage management in conservative and optimistic systems. Proceedings of the ACM Symposium on the Principles of Distributed Computing, Quebec City, Quebec, (1990).","journal-title":"Proceedings of the ACM Symposium on the Principles of Distributed Computing, Quebec City, Quebec"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SIMSYM.1991.151500"},{"key":"e_1_3_3_26_1","article-title":"Virtual Time III: Unified virtual time","author":"Jefferson D. R.","year":"2017","unstructured":"D. R. Jefferson and P. Barnes Jr. 2017. Virtual Time III: Unified virtual time. Proc. of the 2017 Winter Simulation Conference, (W. K. V. Chan, A. D'Ambrogio, G. Zacharewicz, N. Mustafee, G. Wainer, E. Page eds.), Las Vegas, NV, (2017).","journal-title":"Proc. of the 2017 Winter Simulation Conference"},{"key":"e_1_3_3_27_1","doi-asserted-by":"crossref","unstructured":"D. R. Jefferson and P. Barnes Jr. 2022. Virtual Time III Part 2: Combining conservative and optimistic synchronization. Submitted .","DOI":"10.1145\/3505249"},{"key":"e_1_3_3_28_1","unstructured":"D. R. Jefferson and P. Barnes Jr. 2020c. Throttling and Message Cancellation. Submitted ."},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/182478.182480"},{"key":"e_1_3_3_30_1","unstructured":"L. Kal\u00e9 et al. 1993. http:\/\/charm.cs.illinois.edu."},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_3_3_32_1","first-page":"201","article-title":"Determining the global virtual time in a distributed simulation","author":"Lin Y.-B.","year":"1990","unstructured":"Y.-B. Lin and E. Lazowska. 1990. Determining the global virtual time in a distributed simulation. In Proc. of the 19th International Conference on Parallel Processing, 201\u2013209.","journal-title":"Proc. of the 19th International Conference on Parallel Processing"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/102810.102813"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/130611.130612"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/158459.158460"},{"key":"e_1_3_3_36_1","first-page":"630","article-title":"Rollback sometimes works \u2026 if filtered (abstract)","author":"Lubachevsky B.","year":"1989","unstructured":"B. Lubachevsky, A. Schwartz, and A. Weiss. 1989. Rollback sometimes works \u2026 if filtered (abstract). In Proceedings of the 21st Winter Simulation Conference Edited by E. A. MacNair, K. J. Musselman, P. Heidelberger, New York: ACM 630\u2013639.","journal-title":"Proceedings of the 21st Winter Simulation Conference"},{"key":"e_1_3_3_37_1","first-page":"53","article-title":"A lock-free o(1) event pool and its application to share-everything PDES platforms","author":"Marotta R.","year":"2016","unstructured":"R. Marotta, M. Ianni, A. Pellegrini, and F. Quaglia. 2016. A lock-free o(1) event pool and its application to share-everything PDES platforms. In Proceedings of the IEEE\/ACM Symposium on Distributed Simulation and Real Time Applications (DS-RT) 53\u201368.","journal-title":"Proceedings of the IEEE\/ACM Symposium on Distributed Simulation and Real Time Applications (DS-RT)"},{"key":"e_1_3_3_38_1","unstructured":"MPI Forum 1994-present. https:\/\/www.mpi-forum.org."},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/151261.151266"},{"issue":"3","key":"e_1_3_3_40_1","article-title":"Toward a theory of superdense time in simulation models","volume":"30","author":"Nutaro J.","year":"2020","unstructured":"J. Nutaro. 2020. Toward a theory of superdense time in simulation models. ACM Transactions on Modeling and Simulation (TOMACS) 30, 3 (2020).","journal-title":"ACM Transactions on Modeling and Simulation (TOMACS)"},{"issue":"2","key":"e_1_3_3_41_1","article-title":"A fine-grain time-sharing time warp system","volume":"27","author":"Pellegrini A.","year":"2017","unstructured":"A. Pellegrini and F. Quaglia. 2017. A fine-grain time-sharing time warp system. ACM Transactions on Modeling and Simulation (TOMACS) 27, 2 (2017).","journal-title":"ACM Transactions on Modeling and Simulation (TOMACS)"},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.05.003"},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/PADS.2005.1"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.920586"},{"key":"e_1_3_3_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/158459.158474"},{"key":"e_1_3_3_46_1","first-page":"112","article-title":"Cancellation strategies in optimistic execution systems","author":"Reiher R. L.","year":"1990","unstructured":"R. L. Reiher, R. M. Fujimoto, S. Bellenot, and D. R. Jefferson. 1990a. Cancellation strategies in optimistic execution systems. Proceedings of the SCS Multiconference on Distributed Simulation. 112\u2013121.","journal-title":"Proceedings of the SCS Multiconference on Distributed Simulation"},{"key":"e_1_3_3_47_1","article-title":"A spectrum of options for parallel simulation","author":"Reynolds P. F.","year":"1988","unstructured":"P. F. Reynolds. 1988. A spectrum of options for parallel simulation. In Proceedings of the 1988 Winter Simulation Conference, M. Abrams, P. Haigh, and J. Comfort (eds).","journal-title":"Proceedings of the 1988 Winter Simulation Conference"},{"key":"e_1_3_3_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SIMSYM.1996.492147"},{"issue":"4","key":"e_1_3_3_49_1","first-page":"21","article-title":"Transparent optimistic synchronization in the high-level architecture via time-management conversion","volume":"22","author":"Santoro A.","year":"2012","unstructured":"A. Santoro and F. Quaglia. 2012. Transparent optimistic synchronization in the high-level architecture via time-management conversion. ACM Transactions on Modeling and Simulation (TOMACS) 22, 4 (2012), Article 21.","journal-title":"ACM Transactions on Modeling and Simulation (TOMACS)"},{"key":"e_1_3_3_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20860-2_6"},{"key":"e_1_3_3_51_1","first-page":"15","article-title":"Automatic generation of reversible c++ code and its performance in a scalable kinetic Monte-Carlo application","author":"Schordan M.","year":"2016","unstructured":"M. Schordan, T. Oppelstrup, D. R. Jefferson, and P. D. Barnes Jr. 2016. Automatic generation of reversible c++ code and its performance in a scalable kinetic Monte-Carlo application. In Proceedings of the ACM SIGSIM PADS (Banff, Canada), (2016), 15\u201318.","journal-title":"Proceedings of the ACM SIGSIM PADS"},{"key":"e_1_3_3_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/158459.158473"},{"key":"e_1_3_3_53_1","volume-title":"Workshop on Principles of Advanced and Distributed Simulation (PADS\u201905)","author":"Tang Y.","year":"2005","unstructured":"Y. Tang, K. Perumalla, R. Fujimoto, H. Karimabadi, J. Driscoll, and Y. Omelchenko. 2005. Optimistic parallel discrete simulation of physical systems using reverse computation. Workshop on Principles of Advanced and Distributed Simulation (PADS\u201905), Monterey, CA, (2005)."},{"key":"e_1_3_3_54_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549705054931"},{"key":"e_1_3_3_55_1","author":"West D.","year":"1988","unstructured":"D. West. 1988. Optimizing Time Warp: Lazy Rollback and Lazy Reevaluation. Master's Thesis, University of Calgary, Calgary, Alberta, Canada, (1988).","journal-title":"Optimizing Time Warp: Lazy Rollback and Lazy Reevaluation"},{"key":"e_1_3_3_56_1","article-title":"Automatic incremental state saving","author":"West D.","year":"1996","unstructured":"D. West. 1996. Automatic incremental state saving. Proceedings of the 10th Workshop on Parallel and Distributed Simulation, Philadelphia, PA, USA, (1996).","journal-title":"Proceedings of the 10th Workshop on Parallel and Distributed Simulation"},{"key":"e_1_3_3_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1244381.1244404"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505248","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3505248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:26Z","timestamp":1750188686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3505248"],"URL":"https:\/\/doi.org\/10.1145\/3505248","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2020-09-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}