An Efficient Decentralized Algorithm for the Distributed Trigger Counting Problem.

Consider a distributed system with n processors, in which each processor receives some triggers from an external source. The distributed trigger counting problem is to raise an alert and report to a user when the number of triggers received by the system reaches w, where w is a user-specified input. The problem has applications in monitoring, global snapshots, synchronizers and other distributed settings. The main result of the paper is a decentralized and randomized algorithm with expected message complexity O(nlogn logw). Moreover, every processor in this algorithm receives no more than O(logn logw) messages with high probability. All the earlier algorithms for this problem have maximum message load of Ώ(n logw). [ABSTRACT FROM AUTHOR]