{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,9]],"date-time":"2025-11-09T17:56:26Z","timestamp":1762710986001,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"22","license":[{"start":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T00:00:00Z","timestamp":1605052800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2020R1F1A1048443"],"award-info":[{"award-number":["2020R1F1A1048443"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>A distributed trigger counting (DTC) problem is to detect w triggers in the distributed system consisting of n nodes. DTC algorithms can be used for monitoring systems using sensors to detect a significant global change. When designing an efficient DTC algorithm, the following goals should be considered; minimizing the whole number of exchanged messages used for counting triggers and even distribution of communication loads among nodes. In this paper, we present an efficient DTC algorithm, DDR-coin (Deterministic Detection of Randomly generated coins). The message complexity\u2014the total number of exchanged messages\u2014of DDR-coin is O(nlogn(w\/n)) in average. MaxRcvLoad\u2014the maximum number of received messages to detect w triggers in each node\u2014is O(logn(w\/n)) on average. DDR-coin is not an exact algorithm; even though w triggers are received by the n nodes, it can fail to raise an alarm with a negligible probability. However, DDR-coin is more efficient than exact DTC algorithms on average and the gap between those is increased for larger n. We implemented the prototype of the proposed scheme using NetLogo 6.1.1. We confirmed that experimental results are close to our mathematical analysis. Compared with the previous schemes\u2014TreeFill, CoinRand, and RingRand\u2014 DDR-coin shows smaller message complexity and MaxRcvLoad.<\/jats:p>","DOI":"10.3390\/s20226446","type":"journal-article","created":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T19:08:28Z","timestamp":1605121708000},"page":"6446","update-policy":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm"],"prefix":"10.3390","volume":"20","author":[{"given":"Seokhyun","family":"Kim","sequence":"first","affiliation":[{"name":"Coupang Corp., Tower 730, 570 Songpa-daero, Songpa-gu, Seoul 05510, Korea"}]},{"given":"Yongsu","family":"Park","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Hanyang University, Seoul 04763, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/978-3-642-17679-1_5","article-title":"An Efficient Decentralized Algorithm for the Distributed Trigger Counting Problem","volume":"Volume 6522","author":"Chakaravarthy","year":"2011","journal-title":"Lecture Notes in Computer Science"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V.T., Choudhury, A.R., and Sabharwal, Y. (2011, January 16\u201320). Improved algorithms for the distributed trigger counting problem. Proceedings of the 25th IEEE International Parallel & Distributed Processing Symposium, Anchorage, AK, USA.","DOI":"10.1109\/IPDPS.2011.56"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1109\/TPDS.2009.108","article-title":"Efficient algorithms for global snapshots in large distributed systems","volume":"21","author":"Garg","year":"2010","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/214451.214456","article-title":"Distributed snapshots: Determining global states of distributed systems","volume":"3","author":"Chandy","year":"1985","journal-title":"ACM Trans. Comput. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(87)90125-6","article-title":"On distributed snapshots","volume":"25","author":"Lai","year":"1987","journal-title":"Inf. Process. Lett."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1006\/jpdc.1993.1075","article-title":"Efficient algorithms for distributed snapshots and global virtual time approximation","volume":"18","author":"Mattern","year":"1993","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Akanbi, A., and Muthoni Masinde, M. (2020). A Distributed Stream Processing Middleware Framework for Real-Time Analysis of Heterogeneous Data on Big Data Platform: Case of Environmental Monitoring. Sensors, 20.","DOI":"10.3390\/s20113166"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"10048","DOI":"10.3390\/s111110048","article-title":"A Grid-Based Distributed Event Detection Scheme for Wireless Sensor Networks","volume":"11","author":"Ko","year":"2011","journal-title":"Sensors"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Leon-Garcia, F., Palomares, J.M., and Olivares, J. (2018). Data\u2014Domain Reduction Model for Threshold-Based Event Detection in Sensor Networks. Sensors, 18.","DOI":"10.3390\/s18113806"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Papan, J., Segec, P., Yeremenko, O., Bridova, I., and Hodon, M. (2020). Enhanced Multicast Repair Fast Reroute Mechanism for Smart Sensors IoT and Network Infrastructure. Sensors, 20.","DOI":"10.3390\/s20123428"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Tundis, A., Kaleem, H., and M\u00fchlh\u00e4user, M. (2020). Detecting and Tracking Criminals in the Real World through an IoT-Based System. Sensors, 20.","DOI":"10.3390\/s20133795"},{"key":"ref_12","unstructured":"Changlei, L., and Guohong, C. (2010, January 14\u201319). Distributed monitoring and aggregation in wireless sensor networks. Proceedings of the 2010 IEEE INFOCOM, San Diego, CA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1340771.1340775","article-title":"Aggregation methods for large-scale sensor networks","volume":"4","author":"Chitnis","year":"2008","journal-title":"ACM Trans. Sen. Netw."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1016\/j.parco.2004.04.001","article-title":"The ganglia distributed monitoring system: Design, implementation, and experience","volume":"30","author":"Massie","year":"2004","journal-title":"Parallel Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/1113361.1113374","article-title":"Comon: A mostly-scalable monitoring system for planetlab","volume":"40","author":"Park","year":"2006","journal-title":"SIGOPS Oper. Syst. Rev."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1689","DOI":"10.1109\/TWC.2004.833443","article-title":"Dctc: Dynamic convoy tree-based collaboration for target tracking in sensor networks","volume":"3","author":"Wensheng","year":"2004","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kim, S., Lee, J., Park, Y., and Cho, Y. (2013). An optimal distributed trigger counting algorithm for large-scale networked systems. Simulation Trans. Soc. Model. Simul. Int.","DOI":"10.1177\/0037549713485499"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Emek, Y., and Korman, A. (2010, January 25\u201328). Efficient threshold detection in a distributed environment: Extended abstract. Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC \u201910, Zurich, Switzerland.","DOI":"10.1145\/1835698.1835742"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2463","DOI":"10.1002\/wcm.2698","article-title":"Distributed trigger counting algorithms for arbitrary network topology","volume":"16","author":"Chang","year":"2016","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ibe, O.C. (2013). Markov Processes for Stochastic Modeling, Elsevier B.V., Registered Office.","DOI":"10.1016\/B978-0-12-407795-9.00015-3"},{"key":"ref_22","unstructured":"(2020, November 07). NetLogo. Available online: https:\/\/linproxy.fan.workers.dev:443\/http\/ccl.northwestern.edu\/netlogo\/."},{"key":"ref_23","unstructured":"(2020, November 07). Source Code of DDR-coin. Available online: https:\/\/linproxy.fan.workers.dev:443\/https\/github.com\/SeokhyunKim\/dtc-algos."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1281","DOI":"10.1109\/TPDS.2010.24","article-title":"Fast and message-efficient global snapshot algorithms for large-scale distributed systems","volume":"21","author":"Kshemkalyani","year":"2010","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1109\/TPDS.2012.139","article-title":"Flexible symmetrical global-snapshot algorithms for large-scale distributed systems","volume":"24","author":"Tsai","year":"2013","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/www.mdpi.com\/1424-8220\/20\/22\/6446\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:32:13Z","timestamp":1760178733000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/www.mdpi.com\/1424-8220\/20\/22\/6446"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,11]]},"references-count":25,"journal-issue":{"issue":"22","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["s20226446"],"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.3390\/s20226446","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2020,11,11]]}}}