DDR-coin: An Efficient Probabilistic Distributed Trigger Counting Algorithm

Area of Science:

• Distributed Systems
• Sensor Networks
• Algorithm Analysis

Background:

• Distributed trigger counting (DTC) is crucial for monitoring systems using sensors to detect global changes.
• Efficient DTC algorithms require minimizing message complexity and balancing communication loads across nodes.

Purpose of the Study:

• To present an efficient DTC algorithm named DDR-coin.
• To analyze the performance of DDR-coin in terms of message complexity and maximum received load.

Main Methods:

• Developed a novel DTC algorithm, DDR-coin.
• Analyzed the average message complexity as O(nlogn(w/n)).
• Analyzed the average maximum received load (MaxRcvLoad) as O(logn(w/n)).

Main Results:

• DDR-coin achieves an average message complexity of O(nlogn(w/n)) and MaxRcvLoad of O(logn(w/n)).
• The algorithm is probabilistic but has a negligible failure rate.
• Experimental results from a NetLogo prototype align with theoretical analysis.

Conclusions:

• DDR-coin offers superior efficiency compared to existing DTC algorithms like TreeFill, CoinRand, and RingRand.
• The performance advantage of DDR-coin increases with a larger number of nodes (n).
• DDR-coin is a viable and efficient solution for distributed trigger counting in large-scale systems.