Distributed trigger counting (DTC) is a problem related to the detection of triggers with 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 of with high probability. The maximum number of received messages to detect triggers in each node is 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.
MitchellM. Complexity: A Guided Tour. New York: Oxford University Press, 2009.
2.
MillerJHPageSE. Complex Adaptive Systems: An Introduction to Computational Models of Social Life. Princeton, NJ: Princeton University Press, 2007.
3.
FerberJ. Multi-agent Systems: An Introduction to Distributed Artificial Intelligence. Reading, MA: Addison-Wesley, 1999.
4.
GoldmanCVZilbersteinS. Optimizing information exchange in cooperative multi-agent systems. In: Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems. New York: ACM Press, 2003, pp. 137–144.
5.
Olfati-SaberRFaxJAMurrayRM. Consensus and cooperation in networked multi-agent systems. Proc IEEE2007; 95: 215–233.
6.
JanssenMKukG. A complex adaptive system perspective of enterprise architecture in electronic government. In: Proceedings of the 39th Annual Hawaii International Conference on System Sciences, 2006 (HICSS’06), vol. 4. Piscataway, NJ: IEEE Press, 2006, p. 71b.
7.
MassieMLChunBNCullerDE. The ganglia distributed monitoring system: design, implementation, and experience. Parallel Comput2004; 30: 817–840.
8.
ZhangWCaoG. DCTC: dynamic convoy tree-based collaboration for target tracking in sensor networks. IEEE Trans Wireless Commun2004; 3: 1689–1701.
9.
ParkKPaiVS. CoMon: a mostly-scalable monitoring system for PlanetLab. ACM SIGOPS Operat Syst Rev2006; 40: 65–74.
10.
ChitnisLDobraARankaS. Aggregation methods for large-scale sensor networks. ACM Trans Sensor Networks2008; 4(2): 9.
11.
LiuCCaoG. Distributed monitoring and aggregation in wireless sensor networks. In: Proceedings INFOCOM 2010. Piscataway, NJ: IEEE Press, 2010, pp. 1–9.
GargRGargVKSabharwalY. Efficient algorithms for global snapshots in large distributed systems. IEEE Trans Parallel Distrib Syst2010; 21: 620–630.
14.
ChakaravarthyVChoudhuryAGargVSabharwalY. An efficient decentralized algorithm for the distributed trigger counting problem. ICDCN’11 Proceedings of the 12th International Conference on Distributed Computing and Networking. berlin: Springer-Verlag, 2011, pp. 53–64.
15.
ChakaravarthyVTChoudhuryARSabharwalY. Improved algorithms for the distributed trigger counting problem. In: 2011 IEEE International Parallel and Distributed Processing Symposium (IPDPS). Piscataway, NJ: IEEE Press, 2011, pp. 515–523.
16.
KshemkalyaniAD. Fast and message-efficient global snapshot algorithms for large-scale distributed systems. IEEE Trans Parallel Distrib Syst2010; 21: 1281–1289.
17.
TsaiJ. Flexible symmetrical global-snapshot algorithms for large-scale distributed systems. IEEE Trans Parallel Distrib Syst2013; 24: 493–505.
18.
ChandyKMLamportL. Distributed snapshots: determining global states of distributed systems. ACM Trans Comput Syst1985; 3: 63–75.
19.
LaiTHYangTH. On distributed snapshots. Informat Process Lett1987; 25: 153–158.
20.
MatternF. Efficient algorithms for distributed snapshots and global virtual time approximation. J Parallel Distrib Comput1993; 18: 423–434.
21.
EmekYKormanA. Efficient threshold detection in a distributed environment. In: Proceedings of the 29th ACM SIGACT–SIGOPS Symposium on Principles of Distributed Computing. New York: ACM Press, 2010, pp. 183–191.
