An optimal distributed trigger counting algorithm for large-scale networked systems. (July 2013)

• Record Type: Journal Article
• Authors: Kim, Seokhyun; Lee, Jaeheung; Park, Yongsu; Cho, Yookun
• Other Names: Niazi Muaz A. guest-editor.; Hussain Amir guest-editor.
• Is Part Of: Simulation. Volume 89:Number 7(2013)
• Page Start: 846
• Page End: 859
• Publication Date: 2013-07
• Subjects: Distributed trigger counting -- distributed algorithm -- complex adaptive systems -- multi-agent systems -- randomized algorithm -- data aggregation -- distributed systems; Computer simulation -- Periodicals; 003.3
• DOI: 10.1177/0037549713485499
• Languages: English
• ISSNs: 0037-5497

Abstract

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.