Brief Announcement: A Decentralized Algorithm for Distributed Trigger Counting.

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. [ABSTRACT FROM AUTHOR]