DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm.

A distributed trigger counting (DTC) problem is to detect triggers in the distributed system consisting of 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 O(nlogn(w/n)) in average. MaxRcvLoad-the maximum number of received messages to detect triggers in each node-is O(logn(w/n)) on average. DDR-coin is not an exact algorithm; even though triggers are received by the 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 . 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.