DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm
A distributed trigger counting (DTC) problem is to detect <i>w</i> triggers in the distributed system consisting of <i>n</i> nodes. DTC algorithms can be used for monitoring systems using sensors to detect a significant global change. When designing an efficient DTC algorithm...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-11-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/20/22/6446 |
| _version_ | 1827702416343040000 |
|---|---|
| author | Seokhyun Kim Yongsu Park |
| author_facet | Seokhyun Kim Yongsu Park |
| author_sort | Seokhyun Kim |
| collection | DOAJ |
| description | A distributed trigger counting (DTC) problem is to detect <i>w</i> triggers in the distributed system consisting of <i>n</i> 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—the total number of exchanged messages—of DDR-coin is <inline-formula><math display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><msub><mo form="prefix">log</mo><mi>n</mi></msub><mrow><mo>(</mo><mi>w</mi><mo>/</mo><mi>n</mi><mo>)</mo></mrow><mo>)</mo></mrow></semantics></math></inline-formula> in average. MaxRcvLoad—the maximum number of received messages to detect <i>w</i> triggers in each node—is <inline-formula><math display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msub><mo form="prefix">log</mo><mi>n</mi></msub><mrow><mo>(</mo><mi>w</mi><mo>/</mo><mi>n</mi><mo>)</mo></mrow><mo>)</mo></mrow></semantics></math></inline-formula> on average. DDR-coin is not an exact algorithm; even though <i>w</i> triggers are received by the <i>n</i> 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 <i>n</i>. 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—TreeFill, CoinRand, and RingRand— DDR-coin shows smaller message complexity and MaxRcvLoad. |
| first_indexed | 2024-03-10T14:56:02Z |
| format | Article |
| id | doaj.art-9a38e8cd62594f87bc312247bf441b33 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T14:56:02Z |
| publishDate | 2020-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-9a38e8cd62594f87bc312247bf441b332023-11-20T20:37:30ZengMDPI AGSensors1424-82202020-11-012022644610.3390/s20226446DDR-coin: An Efficient Probabilistic Distributed Trigger Counting AlgorithmSeokhyun Kim0Yongsu Park1Coupang Corp., Tower 730, 570 Songpa-daero, Songpa-gu, Seoul 05510, KoreaDepartment of Computer Science, Hanyang University, Seoul 04763, KoreaA distributed trigger counting (DTC) problem is to detect <i>w</i> triggers in the distributed system consisting of <i>n</i> 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—the total number of exchanged messages—of DDR-coin is <inline-formula><math display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><msub><mo form="prefix">log</mo><mi>n</mi></msub><mrow><mo>(</mo><mi>w</mi><mo>/</mo><mi>n</mi><mo>)</mo></mrow><mo>)</mo></mrow></semantics></math></inline-formula> in average. MaxRcvLoad—the maximum number of received messages to detect <i>w</i> triggers in each node—is <inline-formula><math display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msub><mo form="prefix">log</mo><mi>n</mi></msub><mrow><mo>(</mo><mi>w</mi><mo>/</mo><mi>n</mi><mo>)</mo></mrow><mo>)</mo></mrow></semantics></math></inline-formula> on average. DDR-coin is not an exact algorithm; even though <i>w</i> triggers are received by the <i>n</i> 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 <i>n</i>. 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—TreeFill, CoinRand, and RingRand— DDR-coin shows smaller message complexity and MaxRcvLoad.https://www.mdpi.com/1424-8220/20/22/6446distributed trigger countingdistributed algorithmprobabilistic algorithmdistributed systems |
| spellingShingle | Seokhyun Kim Yongsu Park DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm Sensors distributed trigger counting distributed algorithm probabilistic algorithm distributed systems |
| title | DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm |
| title_full | DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm |
| title_fullStr | DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm |
| title_full_unstemmed | DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm |
| title_short | DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm |
| title_sort | ddr coin an efficient probabilistic distributed trigger counting algorithm |
| topic | distributed trigger counting distributed algorithm probabilistic algorithm distributed systems |
| url | https://www.mdpi.com/1424-8220/20/22/6446 |
| work_keys_str_mv | AT seokhyunkim ddrcoinanefficientprobabilisticdistributedtriggercountingalgorithm AT yongsupark ddrcoinanefficientprobabilisticdistributedtriggercountingalgorithm |