An optimal distributed trigger counting algorithm for large-scale networked systems. (July 2013) - Kim, Seokhyun; Lee, Jaeheung; Park, Yongsu; Cho, Yookun
Distributed trigger counting (DTC) is a problem related to the detection ofw triggers withn nodes in large-scale distributed systems that have general characteristics of complex adaptive systems. The triggers come from an external source, and no a priori information about the triggers is given. DTC algorithms can be used for distributed monitoring and global snapshots. When designing an efficient DTC algorithm, the following goals should be considered: minimizing the overall message complexity and distributing the loads for detecting triggers among nodes. In this paper, we propose a randomized algorithm called TreeFill, which satisfies the message complexity ofO ( n log ( w / n ) ) with high probability. The maximum number of received messages to detectw triggers in each node isO ( log ( w / n ) ) with high probability. These results satisfy the lower bounds of DTC problems. We prove the upper bounds of TreeFill . The performance of TreeFill is also evaluated by means of an agent-based simulation using NetLogo. The simulation results show that TreeFill uses about 54–69% of the messages used in a previous work called CoinRand . The maximum number of received messages in each node of TreeFill is also smaller than that in the previous work.