| Summary: | 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.
|
|---|