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(n log n log w). Moreover, every processor in this algorithm receives no more than O(log n log w) messages with high probability. All the earlier algorithms for this problem have maximum message load of Ω(n log w).
['Venkatesan T. Chakaravarthy', 'Anamitra R. Choudhury', 'Vijay K. Garg', 'Yogish Sabharwal']
An efficient decentralized algorithm for the distributed trigger counting problem