Multiobjective message scheduling for Hybrid Synchronization in Distributed Simulations

Paulo Comasetto; Ricardo Parizotto; Braulio Mello

doi:10.5753/jbcs.2024.3197

Authors

Paulo Comasetto Federal University of Fronteira Sul https://orcid.org/0009-0006-4067-3199
Ricardo Parizotto Federal University of Rio Grande do Sul https://orcid.org/0000-0001-8913-5486
Braulio Mello Federal University of Fronteira Sul https://orcid.org/0000-0003-3430-809X

DOI:

https://doi.org/10.5753/jbcs.2024.3197

Keywords:

Distributed Simulation, Hybrid synchronization, Multiobjetive scheduling

Abstract

One of the essential aspects of distributed simulations is to order events according to a causal consistency model. Traditionally, implementing causal consistency can be made using a conservative or optimistic approach. However, traditional techniques are costly in processing time to ensure causality. A promising approach to order events is a hybrid synchronization approach, where processes can change dynamically between optimistic and conservative approaches. Unfortunately, synchronizing processes running a hybrid synchronization is a complex problem. In this work, we discuss a multi-objective scheduling of hybrid synchronization messages problem. Beyond that, we propose using a scheduling algorithm to reach an equilibrium between processing and causality violations and describe how to integrate the algorithm in an existing distributed simulator. The algorithm uses two memoization phases, making the scheduling suitable for a dynamic environment. Finally, to demonstrate the feasibility of our scheduling approach, we implemented it in an existing distributed simulation architecture. Analysis based on the experiments demonstrates the behavior of the simulation regarding the number of discarding/processed messages and work performed.

Downloads

Download data is not yet available.

References

Brown, R. (1988). Calendar queues: a fast 0 (1) priority queue implementation for the simulation event set problem. Communications of the ACM, 31(10):1220-1227. DOI: 10.1145/63039.63045.

Eker, A., Arafa, Y., Badawy, A.-H. A., Santhi, N., Eidenbenz, S., and Ponomarev, D. (2021). Load-aware dynamic time synchronization in parallel discrete event simulation. pages 95-105. DOI: 0.1145/3437959.3459249.

Jefferson, D. R. and Barnes, P. D. (2017). Virtual time iii: unification of conservative and optimistic synchronization in parallel discrete event simulation. In 2017 Winter Simulation Conference (WSC), pages 786-797. IEEE. DOI: 10.1109/WSC.2017.8247832.

Junior, E. M., Terra, A., Parizotto, R., and Mello, B. (2020). Closing the gap between lookahead and checkpointing to provide hybrid synchronization. In Anais do XLVII Seminário Integrado de Software e Hardware, pages 104-115, Porto Alegre, RS, Brasil. SBC. DOI: 10.5753/semish.2020.11321.

Kleinberg, J. and Tardos, E. (2006). Algorithm design. Pearson Education India. Book.

Kolen, A. W., Lenstra, J. K., Papadimitriou, C. H., and Spieksma, F. C. (2007). Interval scheduling: A survey. Naval Research Logistics (NRL), 54(5):530-543. DOI: 10.1002/nav.20231.

Mello, B. A. and Wagner, F. R. (2002). A standardized co-simulation backbone. In SoC Design Methodologies, pages 181-192. Springer. DOI: 10.1007/978-0-387-35597-9_16.

Parizotto, R. and Mello, B. (2022). Multiobjective scheduling of hybrid synchronization messages. In Anais do XLIX Seminário Integrado de Software e Hardware, pages 49-57, Porto Alegre, RS, Brasil. SBC. DOI: 10.5753/semish.2022.222591.

Perumalla, K. S. (2005). /spl mu/sik-a micro-kernel for parallel/distributed simulation systems. In Workshop on Principles of Advanced and Distributed Simulation (PADS'05), pages 59-68. IEEE. DOI: 10.1109/PADS.2005.1.

Santoro, T. and Quaglia, F. (2010). A low-overhead constant-time ltf scheduler for optimistic simulation systems. In The IEEE symposium on Computers and Communications, pages 948-953. IEEE. DOI: 10.1109/ISCC.2010.5546544.

Som, T. K. and Sargent, R. G. (1998). A probabilistic event scheduling policy for optimistic parallel discrete event simulation. In Proceedings of the Twelfth Workshop on Parallel and Distributed Simulation, PADS '98, page 56–63, USA. IEEE Computer Society. Available online [link].

Taylor, S. J. (2019). Distributed simulation: state-of-the-art and potential for operational research. European Journal of Operational Research, 273(1):1-19. DOI: 10.1016/j.ejor.2018.04.032.