{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T03:47:03Z","timestamp":1782877623436,"version":"3.54.5"},"reference-count":86,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-1936522"],"award-info":[{"award-number":["CCF-1936522"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>Distributed software systems are increasingly developed and deployed today. Many of these systems are supposed to run continuously. Given their critical roles in our society and daily lives, assuring the quality of distributed systems is crucial. Analyzing runtime program dependencies has long been a fundamental technique underlying numerous tool support for software quality assurance. Yet conventional approaches to dynamic dependence analysis face severe scalability barriers when they are applied to real-world distributed systems, due to the unbounded executions to be analyzed in addition to common efficiency challenges suffered by dynamic analysis in general.<\/jats:p>\n          <jats:p>\n            In this article, we present S\n            <jats:sc>EADS<\/jats:sc>\n            , a\n            <jats:italic>distributed<\/jats:italic>\n            ,\n            <jats:italic>online<\/jats:italic>\n            , and\n            <jats:italic>cost-effective<\/jats:italic>\n            dynamic dependence analysis framework that aims at scaling the analysis to real-world distributed systems. The analysis itself is distributed to exploit the distributed computing resources (e.g., a cluster) of the system under analysis; it works online to overcome the problem with unbounded execution traces while running continuously with the system being analyzed to provide timely querying of analysis results (i.e., runtime dependence set of any given query). Most importantly, given a user-specified time budget, the analysis automatically adjusts itself to better cost-effectiveness tradeoffs (than otherwise) while respecting the budget by changing various analysis parameters according to the time being spent by the dependence analysis. At the core of the automatic adjustment is our application of a reinforcement learning method for the decision making\u2014deciding which configuration to adjust to according to the current configuration and its associated analysis cost with respect to the user budget. We have implemented S\n            <jats:sc>EADS<\/jats:sc>\n            for Java and applied it to eight real-world distributed systems with continuous executions. Our empirical results revealed the efficiency and scalability advantages of our framework over a conventional dynamic analysis, at least for dynamic dependence computation at method level. While we demonstrate it in the context of dynamic dependence analysis in this article, the\n            <jats:italic>methodology<\/jats:italic>\n            for achieving and maintaining scalability and greater cost-effectiveness against continuously running systems is more broadly applicable to other dynamic analyses.\n          <\/jats:p>","DOI":"10.1145\/3379345","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:39:27Z","timestamp":1594125567000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["S\n            <scp>EADS<\/scp>"],"prefix":"10.1145","volume":"30","author":[{"given":"Xiaoqin","family":"Fu","sequence":"first","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Washington State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5224-9970","authenticated-orcid":false,"given":"Haipeng","family":"Cai","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Washington State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wen","family":"Li","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Washington State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2990-1614","authenticated-orcid":false,"given":"Li","family":"Li","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Monash University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems. 550--557","author":"David"},{"key":"e_1_2_1_2_1","unstructured":"Apache. 2015. ZooKeeper. Retrieved from https:\/\/zookeeper.apache.org\/.  Apache. 2015. ZooKeeper. Retrieved from https:\/\/zookeeper.apache.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Apache. 2017. Voldemort. Retrieved from https:\/\/github.com\/voldemort.  Apache. 2017. Voldemort. Retrieved from https:\/\/github.com\/voldemort."},{"key":"e_1_2_1_4_1","unstructured":"Apache. 2017. The Voldemort Project. Retrieved from https:\/\/www.project-voldemort.com\/voldemort\/.  Apache. 2017. The Voldemort Project. Retrieved from https:\/\/www.project-voldemort.com\/voldemort\/."},{"key":"e_1_2_1_5_1","unstructured":"Apache. 2018. Thrift. Retrieved from https:\/\/thrift.apache.org\/.  Apache. 2018. Thrift. Retrieved from https:\/\/thrift.apache.org\/."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Software Engineering. 432--441","author":"Apiwattanapong Taweesup","year":"2005"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation","volume":"10","author":"Attariyan Mona","year":"2010"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85502-6_4"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the SBMO\/IEEE MTT-S International Microwave 8 Optoelectronics Conference (IMOC\u201913)","author":"Barboza Erick"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-sen.2010.0141"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0362-546X(89)90096-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.012"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183399.3183401"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2017.2692783"},{"key":"e_1_2_1_15_1","volume-title":"DABS: A Framework for Dynamic Dependence Analysis of Distributed Programs. Technical Report","author":"Cai Haipeng","year":"2020"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2642937.2642950"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SANER.2015.7081862"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2894751"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970352"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2018.05.025"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/337180.337234"},{"key":"e_1_2_1_22_1","volume-title":"Distributed Systems: Concepts and Design","author":"Coulouris George","year":"2011","edition":"5"},{"key":"e_1_2_1_23_1","unstructured":"Manoj Debnath. 2018. Understanding asynchronous socket channels in Java. Retrieved from https:\/\/www.developer.com\/java\/data\/understanding-asynchronous-socket-channels-in-java.html.  Manoj Debnath. 2018. Understanding asynchronous socket channels in Java. Retrieved from https:\/\/www.developer.com\/java\/data\/understanding-asynchronous-socket-channels-in-java.html."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442176"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the European Conference on Object-oriented Programming. 570--594","author":"Eugster Patrick"},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Learning rates for q-learning","author":"Even-Dar Eyal","year":"2003","journal-title":"J. Mach. Learn. Res. 5"},{"key":"e_1_2_1_27_1","volume-title":"Self-adapt hybrid chaotic neural network and its application to TSP. J. Syst. Simul. 12","author":"Wei Guo","year":"2006"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2015.2421318"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3341179"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPC.2019.00051"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377812.3390910"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10015-010-0822-7"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491462"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2004.175"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10515-009-0048-x"},{"key":"e_1_2_1_36_1","unstructured":"GoogleCode. 2015. MultiChat. Retrieved from https:\/\/code.google.com\/p\/multithread-chat-server\/.  GoogleCode. 2015. MultiChat. Retrieved from https:\/\/code.google.com\/p\/multithread-chat-server\/."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44467-X_2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-009-0086-1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2019.00027"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/143062.143156"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/77606.77608"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMPSAC.2019.00073"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005770"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the USENIX Annual Technical Conference","volume":"8","author":"Hunt Patrick","year":"2010"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/336512.336545"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2002259.2002278"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the ACM SIGPLAN\/SIGOPS International Conference on Virtual Execution Environments","volume":"47","author":"Kemerlis Vasileios P."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90054-3"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOSE.2007.19"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357390.3361028"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/940071.940096"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 9th Yale Workshop on Adaptive and Learning Systems. 101--105","author":"Kuvayev Leonid"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the Cetus Users and Compiler Infrastructure Workshop. 1--11","author":"Lam Patrick","year":"2011"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2010.2043839"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the International Conference on Machine Learning","volume":"96","author":"Michael"},{"key":"e_1_2_1_56_1","unstructured":"Wes Masri. 2015. Dependence Analysis. Retrieved from https:\/\/www.sciencedirect.com\/topics\/computer-science\/dependence-analysis.  Wes Masri. 2015. Dependence Analysis. Retrieved from https:\/\/www.sciencedirect.com\/topics\/computer-science\/dependence-analysis."},{"key":"e_1_2_1_57_1","volume-title":"Distributed Event-based Systems","author":"M\u00fchl Gero"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186632.1186636"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Software Engineering. 177--186","author":"Oreizy Peyman"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00114731"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.58784"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2335484.2335511"},{"key":"e_1_2_1_63_1","volume-title":"Netty: Home.","author":"Netty","year":"2020"},{"key":"e_1_2_1_64_1","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman Martin L."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-007-0043-0"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.3233\/IDA-163196"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/SERVICES.2019.00088"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLOUD.2019.00061"},{"key":"e_1_2_1_70_1","volume-title":"Compiler Construction","author":"Ryder Barbara"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2017.2704579"},{"key":"e_1_2_1_72_1","unstructured":"SourceForge. 2015. NioEcho. Retrieved from http:\/\/rox-xmlrpc.sourceforge.net\/niotut\/index.html# The code.  SourceForge. 2015. NioEcho. Retrieved from http:\/\/rox-xmlrpc.sourceforge.net\/niotut\/index.html# The code."},{"key":"e_1_2_1_73_1","volume-title":"Barto","author":"Sutton Richard S.","year":"2018"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554850.2554955"},{"key":"e_1_2_1_75_1","unstructured":"Bamberg University. 2015. Open Chord. Retrieved from http:\/\/sourceforge.net\/projects\/open-chord\/.  Bamberg University. 2015. Open Chord. Retrieved from http:\/\/sourceforge.net\/projects\/open-chord\/."},{"key":"e_1_2_1_76_1","unstructured":"Vice. 2018. xSocket. Retrieved from http:\/\/xsocket.org\/.  Vice. 2018. xSocket. Retrieved from http:\/\/xsocket.org\/."},{"key":"e_1_2_1_77_1","unstructured":"Andre Violante. 2019. Towards Data Science Simple Reinforcement Learning: Q-learning. Retrieved from https:\/\/towardsdatascience.com\/simple-reinforcement-learning-q-learning-fcddc4b6fe56.  Andre Violante. 2019. Towards Data Science Simple Reinforcement Learning: Q-learning. Retrieved from https:\/\/towardsdatascience.com\/simple-reinforcement-learning-q-learning-fcddc4b6fe56."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSESS.2017.8342969"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992698"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2004.1380086"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168260.2168268"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.5555\/330775"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2016.2521368"},{"key":"e_1_2_1_84_1","volume-title":"Proceedings of the International Conference on Machine Learning. 1167--1174","author":"Wunder Michael","year":"2010"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSME.2017.29"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996855"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAC.2017.47"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379345","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379345","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3379345","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:51Z","timestamp":1750199931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3379345"}},"subtitle":["Scalable and Cost-effective Dynamic Dependence Analysis of Distributed Systems via Reinforcement Learning"],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":86,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3379345"],"URL":"https:\/\/doi.org\/10.1145\/3379345","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,31]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}