{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T13:44:27Z","timestamp":1777902267724,"version":"3.51.4"},"reference-count":22,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T00:00:00Z","timestamp":1368748800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["SIMULATION"],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>Distributed trigger counting (DTC) is a problem related to the detection of [Formula: see text] triggers with [Formula: see text] nodes in large-scale distributed systems that have general characteristics of complex adaptive systems. The triggers come from an external source, and no a priori information about the triggers is given. DTC algorithms can be used for distributed monitoring and global snapshots. When designing an efficient DTC algorithm, the following goals should be considered: minimizing the overall message complexity and distributing the loads for detecting triggers among nodes. In this paper, we propose a randomized algorithm called TreeFill, which satisfies the message complexity of [Formula: see text] with high probability. The maximum number of received messages to detect [Formula: see text] triggers in each node is [Formula: see text] with high probability. These results satisfy the lower bounds of DTC problems. We prove the upper bounds of TreeFill. The performance of TreeFill is also evaluated by means of an agent-based simulation using NetLogo. The simulation results show that TreeFill uses about 54\u201369% of the messages used in a previous work called CoinRand. The maximum number of received messages in each node of TreeFill is also smaller than that in the previous work.<\/jats:p>","DOI":"10.1177\/0037549713485499","type":"journal-article","created":{"date-parts":[[2013,5,18]],"date-time":"2013-05-18T02:39:39Z","timestamp":1368844779000},"page":"846-859","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":5,"title":["An optimal distributed trigger counting algorithm for large-scale networked systems"],"prefix":"10.1177","volume":"89","author":[{"given":"Seokhyun","family":"Kim","sequence":"first","affiliation":[{"name":"School of Computer Science & Engineering, Seoul National University, Seoul, Korea"}]},{"given":"Jaeheung","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Computer Science & Engineering, Seoul National University, Seoul, Korea"}]},{"given":"Yongsu","family":"Park","sequence":"additional","affiliation":[{"name":"Division of Computer Science & Engineering, Hanyang University, Seoul, Korea"}]},{"given":"Yookun","family":"Cho","sequence":"additional","affiliation":[{"name":"School of Computer Science & Engineering, Seoul National University, Seoul, Korea"}]}],"member":"179","published-online":{"date-parts":[[2013,5,17]]},"reference":[{"key":"bibr1-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195124415.001.0001"},{"key":"bibr2-0037549713485499","volume-title":"Complex Adaptive Systems: An Introduction to Computational Models of Social Life","author":"Miller JH","year":"2007"},{"key":"bibr3-0037549713485499","volume-title":"Multi-agent Systems: An Introduction to Distributed Artificial Intelligence","author":"Ferber J","year":"1999"},{"key":"bibr4-0037549713485499","first-page":"137","volume-title":"Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems","author":"Goldman CV"},{"key":"bibr5-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.887293"},{"key":"bibr6-0037549713485499","first-page":"71b","volume-title":"Proceedings of the 39th Annual Hawaii International Conference on System Sciences, 2006 (HICSS\u201906)","volume":"4","author":"Janssen M"},{"key":"bibr7-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2004.04.001"},{"key":"bibr8-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2004.833443"},{"key":"bibr9-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1145\/1113361.1113374"},{"key":"bibr10-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1145\/1340771.1340775"},{"key":"bibr11-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462033"},{"key":"bibr12-0037549713485499","unstructured":"Ganglia Monitoring System. http:\/\/ganglia.sourceforge.net."},{"key":"bibr13-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.108"},{"key":"bibr14-0037549713485499","first-page":"53","volume-title":"ICDCN\u201911 Proceedings of the 12th International Conference on Distributed Computing and Networking","author":"Chakaravarthy V"},{"key":"bibr15-0037549713485499","first-page":"515","volume-title":"2011 IEEE International Parallel and Distributed Processing Symposium (IPDPS)","author":"Chakaravarthy VT"},{"key":"bibr16-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.24"},{"key":"bibr17-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.139"},{"key":"bibr18-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1145\/214451.214456"},{"key":"bibr19-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90125-6"},{"key":"bibr20-0037549713485499","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1993.1075"},{"key":"bibr21-0037549713485499","first-page":"183","volume-title":"Proceedings of the 29th ACM SIGACT\u2013SIGOPS Symposium on Principles of Distributed Computing","author":"Emek Y"},{"key":"bibr22-0037549713485499","unstructured":"NetLogo. http:\/\/ccl.northwestern.edu\/net\\logo\/."}],"container-title":["SIMULATION"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0037549713485499","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0037549713485499","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0037549713485499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T11:24:40Z","timestamp":1777634680000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0037549713485499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,17]]},"references-count":22,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.1177\/0037549713485499"],"URL":"https:\/\/doi.org\/10.1177\/0037549713485499","relation":{},"ISSN":["0037-5497","1741-3133"],"issn-type":[{"value":"0037-5497","type":"print"},{"value":"1741-3133","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,17]]}}}