We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Efficient Decentralized Algorithms for the Distributed Trigger Counting Problem.
- Authors
Chakaravarthy, Venkatesan; Choudhury, Anamitra; Garg, Vijay; Sabharwal, Yogish
- Abstract
Consider a distributed system with n processors, in which each processor receives some triggers from an external source. The distributed trigger counting (DTC) 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. In this paper, we first present a randomized and decentralized algorithm for the DTC problem with message complexity O( nlog nlog w); furthermore, with high probability, no processor receives more than O(log nlog w) messages. Building on the ideas of this algorithm, we develop an improved algorithm having message complexity O( nlog w); furthermore, with high probability, no processor receives more than O(log w) messages. However, neither of the two algorithms provide any bound on the messages sent per processors. These algorithm assume complete connectivity between the processors. Next, we present a third algorithm having message complexity O( nlog nlog w), wherein no processor exchanges more than O(log nlog w) messages with high probability; however, there is a negligible failure probability in raising the alert on receiving w triggers. This algorithm only requires that a constant degree tree be embeddable in the underlying communication graph.
- Subjects
COMPUTER algorithms; COMPUTATIONAL complexity; PROBABILITY theory; MACRO processors; COMPUTER users; ELECTRONIC data processing; MACHINE theory
- Publication
Theory of Computing Systems, 2012, Vol 51, Issue 4, p447
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-012-9405-4