{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T20:47:44Z","timestamp":1740170864404,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,26]],"date-time":"2019-12-26T00:00:00Z","timestamp":1577318400000},"content-version":"vor","delay-in-days":25,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Adapt Syst Model"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>With the decline of Moore\u2019s law and the ever increasing availability of cheap massively parallel hardware, it becomes more and more important to embrace parallel programming methods to implement Agent-Based Simulations (ABS). This has been acknowledged in the field a while ago and numerous research on distributed parallel ABS exists, focusing primarily on Parallel Discrete Event Simulation as the underlying mechanism. However, these concepts and tools are inherently difficult to master and apply and often an excess in case implementers simply want to parallelise their own, custom agent-based model implementation. However, with the established programming languages in the field, Python, Java and C++, it is not easy to address the complexities of parallel programming due to unrestricted side effects and the intricacies of low-level locking semantics. Therefore, in this paper we propose the use of a lock-free approach to parallel ABS using Software Transactional Memory (STM) in conjunction with the pure functional programming language Haskell, which in combination, removes some of the problems and complexities of parallel implementations in imperative approaches. We present two case studies, in which we compare the performance of lock-based and lock-free STM implementations in two different well known Agent-Based Models, where we investigate both the scaling performance under increasing number of CPU cores and the scaling performance under increasing number of agents. We show that the lock-free STM implementations consistently outperform the lock-based ones and scale much better to increasing number of CPU cores both on local hardware and on Amazon EC. Further, by utilizing the pure functional language Haskell we gain the benefits of immutable data and lack of unrestricted side effects guaranteed at compile-time, making validation easier and leading to increased confidence in the correctness of an implementation, something of fundamental importance and benefit in parallel programming in general and scientific computing like ABS in particular.<\/jats:p>","DOI":"10.1186\/s40294-019-0067-9","type":"journal-article","created":{"date-parts":[[2019,12,26]],"date-time":"2019-12-26T17:02:34Z","timestamp":1577379754000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A tale of lock-free agents: towards Software Transactional Memory in parallel Agent-Based Simulation"],"prefix":"10.1186","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8736-0479","authenticated-orcid":false,"given":"Jonathan","family":"Thaler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peer-Olaf","family":"Siebers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,26]]},"reference":[{"key":"67_CR1","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.cosrev.2017.03.001","volume":"24","author":"S Abar","year":"2017","unstructured":"Abar S, Theodoropoulos GK, Lemarinier P, O\u2019Hare GMP (2017) Agent based modelling and simulation tools: a review of the state-of-art software. Comput Sci Rev 24:13\u201333","journal-title":"Comput Sci Rev"},{"key":"67_CR2","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1086.001.0001","volume-title":"Actors: a model of concurrent computation in distributed systems","author":"G Agha","year":"1986","unstructured":"Agha G (1986) Actors: a model of concurrent computation in distributed systems. MIT Press, Cambridge"},{"unstructured":"Bezirgiannis N (2013) Improving performance of simulation software using Haskells concurrency & parallelism. Ph.D. Thesis, Utrecht University - Dept. of Information and Computing Sciences","key":"67_CR3"},{"unstructured":"Breitner J (2019) stm-stats library. http:\/\/hackage.haskell.org\/package\/stm-stats. http:\/\/hackage.haskell.org\/package\/stm-stats. Accessed 4 Dec 2019","key":"67_CR4"},{"issue":"3","key":"67_CR5","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1002\/cpe.3254","volume":"27","author":"F Cicirelli","year":"2015","unstructured":"Cicirelli F, Giordano A, Nigro L (2015) Efficient environment management for distributed simulation of large-scale situated multi-agent systems. Concurr Comput Pract Exp 27(3):610\u2013632. https:\/\/doi.org\/10.1002\/cpe.3254","journal-title":"Concurr Comput Pract Exp"},{"key":"67_CR6","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/11737414_6","volume-title":"Functional and Logic Programming","author":"Anthony Discolo","year":"2006","unstructured":"Discolo A, Harris T, Marlow S, Jones SP, Singh S (2006) Lock free data structures using STM in Haskell. In: Proceedings of the 8th international conference on functional and logic programming. FLOPS\u201906. Springer, Berlin, pp 65\u201380. https:\/\/doi.org\/10.1007\/11737414_6"},{"key":"67_CR7","volume-title":"It\u2019s a nonlinear world","author":"RH Enns","year":"2010","unstructured":"Enns RH (2010) It\u2019s a nonlinear world, 1st edn. Springer Publishing Company, Incorporated, New York","edition":"1"},{"key":"67_CR8","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3374.001.0001","volume-title":"Growing artificial societies: social science from the bottom up","author":"JM Epstein","year":"1996","unstructured":"Epstein JM, Axtell R (1996) Growing artificial societies: social science from the bottom up. The Brookings Institution, Washington"},{"doi-asserted-by":"publisher","unstructured":"Gasser L, Kakugawa K (2002) MACE3J: Fast flexible distributed simulation of large, large-grain multi-agent systems. In: Proceedings of the first international joint conference on autonomous agents and multiagent systems: part 2. AAMAS \u201902. New York: ACM, pp 745\u2013752. Event-place, Bologna. https:\/\/doi.org\/10.1145\/544862.544918","key":"67_CR9","DOI":"10.1145\/544862.544918"},{"doi-asserted-by":"publisher","unstructured":"Gorur BK, Imre K, Oguztuzun H, Yilmaz L (2016) Repast HPC with optimistic time management. In: Proceedings of the 24th high performance computing symposium. HPC \u201916. Society for Computer Simulation International, San Diego, pp 4:1\u20134:9. Event-place, Pasadena. https:\/\/doi.org\/10.22360\/SpringSim.2016.HPC.046","key":"67_CR10","DOI":"10.22360\/SpringSim.2016.HPC.046"},{"unstructured":"Harris T, Peyton\u00a0Jones S (2006) Transactional memory with data invariants. In: First ACM SIGPLAN workshop on languages, compilers, and hardware support for transactional computing (TRANSACT\u201906). https:\/\/www.microsoft.com\/en-us\/research\/publication\/transactional-memory-data-invariants\/. Accessed 4 Dec 2019","key":"67_CR11"},{"doi-asserted-by":"publisher","unstructured":"Harris T, Marlow S, Peyton-Jones S, Herlihy M (2005) Composable memory transactions. In: Proceedings of the tenth ACM SIGPLAN symposium on principles and practice of parallel programming. PPoPP \u201905. ACM, New York, pp 48\u201360. https:\/\/doi.org\/10.1145\/1065944.1065952","key":"67_CR12","DOI":"10.1145\/1065944.1065952"},{"doi-asserted-by":"publisher","unstructured":"Hay J, Wilsey PA (2015) Experiments with hardware-based transactional memory in parallel simulation. In: Proceedings of the 3rd ACM SIGSIM conference on principles of advanced discrete simulation. SIGSIM PADS \u201915. ACM, New York, pp 75\u201386. Event-place, London. https:\/\/doi.org\/10.1145\/2769458.2769462","key":"67_CR13","DOI":"10.1145\/2769458.2769462"},{"doi-asserted-by":"crossref","unstructured":"Himmelspach J, Uhrmacher AM (2007) Plug\u2019n simulate. In: 40th annual simulation symposium (ANSS\u201907), pp 137\u2013143. ISSN: 1080-241X","key":"67_CR14","DOI":"10.1109\/ANSS.2007.34"},{"doi-asserted-by":"publisher","unstructured":"Hudak P, Hughes J, Peyton Jones S, Wadler P (2007) A history of Haskell: being lazy with class. In: Proceedings of the third ACM SIGPLAN conference on history of programming languages. HOPL III. ACM, New York, pp 12-1\u201312-55. https:\/\/doi.org\/10.1145\/1238844.1238856","key":"67_CR15","DOI":"10.1145\/1238844.1238856"},{"issue":"772","key":"67_CR16","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1098\/rspa.1927.0118","volume":"115","author":"WO Kermack","year":"1927","unstructured":"Kermack WO, McKendrick AG (1927) A contribution to the mathematical theory of epidemics. Proc R Soc Lond A Math Phys Eng Sci 115(772):700\u2013721","journal-title":"Proc R Soc Lond A Math Phys Eng Sci"},{"issue":"10\u201311","key":"67_CR17","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1177\/0037549708096691","volume":"84","author":"M Lees","year":"2008","unstructured":"Lees M, Logan B, Theodoropoulos G (2008) Using access patterns to analyze the performance of optimistic synchronization algorithms in simulations of MAS. Simulation 84(10\u201311):481\u2013492. https:\/\/doi.org\/10.1177\/0037549708096691","journal-title":"Simulation"},{"unstructured":"libraries@haskell.org. array: mutable and immutable arrays; 2019. http:\/\/hackage.haskell.org\/package\/array. Accessed 4 Dec 2019","key":"67_CR18"},{"issue":"2","key":"67_CR19","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1109\/5.910853","volume":"89","author":"B Logan","year":"2001","unstructured":"Logan B, Theodoropoulos G (2001) The distributed simulation of multiagent systems. Proc IEEE 89(2):174\u2013185","journal-title":"Proc IEEE"},{"issue":"4","key":"67_CR20","first-page":"10","volume":"11","author":"M Lysenko","year":"2008","unstructured":"Lysenko M, D\u2019Souza RM (2008) A framework for megascale agent based model simulations on graphics processing units. J Artif Soc Soc Simul 11(4):10","journal-title":"J Artif Soc Soc Simul"},{"doi-asserted-by":"crossref","unstructured":"Macal CM (2010) To agent-based simulation from system dynamics. In: Proceedings of the winter simulation conference. WSC '10. Winter simulation conference, Baltimore","key":"#cr-split#-67_CR21.1","DOI":"10.1109\/WSC.2010.5679148"},{"unstructured":"2010, pp 371-382. http:\/\/dl.acm.org\/citation.cfm?id=2433508.2433551. Accessed 4 Dec 2019","key":"#cr-split#-67_CR21.2"},{"issue":"2","key":"67_CR22","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1057\/jos.2016.7","volume":"10","author":"CM Macal","year":"2016","unstructured":"Macal CM (2016) Everything you need to know about agent-based modelling and simulation. J Simul 10(2):144\u2013156","journal-title":"J Simul"},{"unstructured":"Marlow S (2013) Parallel and concurrent programming in Haskell. O\u2019Reilly; Google-Books-ID: k0W6AQAACAAJ","key":"67_CR23"},{"doi-asserted-by":"publisher","unstructured":"Marlow S, Peyton\u00a0Jones S, Singh S (2009) Runtime support for multicore Haskell. In: Proceedings of the 14th ACM SIGPLAN international conference on functional programming. ICFP \u201909. ACM, New York, pp 65\u201378. https:\/\/doi.org\/10.1145\/1596550.1596563","key":"67_CR24","DOI":"10.1145\/1596550.1596563"},{"key":"67_CR25","first-page":"3","volume-title":"Multi-agent-based simulation XV. Lecture notes in computer science","author":"R Meyer","year":"2014","unstructured":"Meyer R (2014) Event-driven multi-agent simulation. Multi-agent-based simulation XV. Lecture notes in computer science. Springer, Cham, pp 3\u201316"},{"issue":"10","key":"67_CR26","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1002\/cpe.1280","volume":"20","author":"R Minson","year":"2008","unstructured":"Minson R, Theodoropoulos GK (2008) Distributing RePast agent-based simulations with HLA. Concurr Comput Pract Exp 20(10):1225\u20131256","journal-title":"Concurr Comput Pract Exp"},{"unstructured":"O\u2019Sullivan B (2014a) Citerion: a Haskell microbenchmarking library; 2014. http:\/\/www.serpentine.com\/criterion\/. Accessed 4 Dec 2019","key":"67_CR27"},{"unstructured":"O\u2019Sullivan B (2014b) Criterion robust, reliable performance measurement and analysis; 2014b. http:\/\/hackage.haskell.org\/package\/criterion. Accessed 4 Dec 2019","key":"67_CR28"},{"doi-asserted-by":"publisher","unstructured":"Perfumo C, S\u00f6nmez N, Stipic S, Unsal O, Cristal A, Harris T, et\u00a0al (2008) The limits of software transactional memory (STM): dissecting Haskell STM applications on a many-core environment. In: Proceedings of the 5th conference on computing frontiers. CF \u201908. ACM, New York, pp 67\u201378. https:\/\/doi.org\/10.1145\/1366230.1366241","key":"67_CR29","DOI":"10.1145\/1366230.1366241"},{"unstructured":"Riley PF, Riley GF (2003) Next generation modeling III-agents: Spades-a distributed agent simulation environment with software-in-the-loop Execution. In: Proceedings of the 35th conference on winter simulation: driving innovation. WSC '03. Winter simulation conference","key":"#cr-split#-67_CR30.1"},{"unstructured":"pp 817-825. Event-place, New Orleans. http:\/\/dl.acm.org\/citation.cfm?id=1030818.1030926. Accessed 4 Dec 2019","key":"#cr-split#-67_CR30.2"},{"doi-asserted-by":"publisher","unstructured":"Shavit N, Touitou D (1995) Software transactional memory. In: Proceedings of the fourteenth annual ACM symposium on principles of distributed computing. PODC \u201995. ACM, New York, pp 204\u2013213. https:\/\/doi.org\/10.1145\/224964.224987","key":"67_CR31","DOI":"10.1145\/224964.224987"},{"issue":"4","key":"67_CR32","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/2517449","volume":"23","author":"V Suryanarayanan","year":"2013","unstructured":"Suryanarayanan V, Theodoropoulos G (2013) Synchronised range queries in distributed simulations of multiagent systems. ACM Trans Model Comput Simul 23(4):25:1\u201325:25. https:\/\/doi.org\/10.1145\/2517449","journal-title":"ACM Trans Model Comput Simul"},{"key":"67_CR33","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/j.procs.2013.05.231","volume":"18","author":"V Suryanarayanan","year":"2013","unstructured":"Suryanarayanan V, Theodoropoulos G, Lees M (2013) PDES-MAS: distributed simulation of multi-agent systems. Procedia Comput Sci 18:671\u2013681","journal-title":"Procedia Comput Sci"},{"unstructured":"Thaler J (2019a) Repository of STM implementations of the agent-based SIR model in Haskell. https:\/\/github.com\/thalerjonathan\/haskell-stm-sir. Accessed 4 Dec 2019","key":"67_CR34"},{"unstructured":"Thaler J (2019b) Repository of STM implementations of the Sugarscape model in Haskell. https:\/\/github.com\/thalerjonathan\/haskell-stm-sugarscape. Accessed 4 Dec 2019","key":"67_CR35"},{"doi-asserted-by":"crossref","unstructured":"Thaler J, Siebers PO (2017) The Art Of Iterating: update-strategies in agent-based. Springer proceedings in complexity. Springer International Publishing, Dublin. https:\/\/www.springer.com\/gp\/book\/9783030302979. Accessed 4 Dec 2019","key":"67_CR36","DOI":"10.1007\/978-3-030-30298-6_3"},{"unstructured":"Thaler J, Siebers PO (2019) Show me your properties: the potential of property-based testing in agent-based simulation. In: Proceedings of the 2019 summer simulation conference. SummerSim \u201919. Society for Computer Simulation International, San Diego, pp 1:1\u20131:12. http:\/\/dl.acm.org\/citation.cfm?id=3374138.3374139. Accessed 4 Dec 2019","key":"67_CR37"},{"doi-asserted-by":"publisher","unstructured":"Thaler J, Altenkirch T, Siebers PO (2018) Pure functional epidemics: an agent-based approach. In: Proceedings of the 30th symposium on implementation and application of functional languages. ACM, IFL New York; 2018, pp 1\u201312. Event-place, Lowell. https:\/\/doi.org\/10.1145\/3310232.3310372","key":"67_CR38","DOI":"10.1145\/3310232.3310372"},{"unstructured":"van Dijk B, van Dijk J (2019) concurrent-extra library; 2018. http:\/\/hackage.haskell.org\/package\/concurrent-extra. Accessed 4 Dec 2019","key":"67_CR39"},{"unstructured":"Wilensky U, Rand W (2015) An introduction to agent-based modeling: modeling natural, social, and engineered complex systems with NETLogo. MIT Press. https:\/\/www.amazon.co.uk\/Introduction-Agent-Based-Modeling-Natural-Engineered\/dp\/0262731894. Accessed 4 Dec 2019","key":"67_CR40"},{"key":"67_CR41","volume-title":"An introduction to multiagent systems","author":"M Wooldridge","year":"2009","unstructured":"Wooldridge M (2009) An introduction to multiagent systems, 2nd edn. Wiley, Hoboken","edition":"2"}],"container-title":["Complex Adaptive Systems Modeling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40294-019-0067-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s40294-019-0067-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40294-019-0067-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T06:55:36Z","timestamp":1627628136000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s40294-019-0067-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["67"],"URL":"https:\/\/doi.org\/10.1186\/s40294-019-0067-9","relation":{},"ISSN":["2194-3206"],"issn-type":[{"type":"electronic","value":"2194-3206"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"5 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"5"}}