On the Distributed Trigger Counting Problem for Dynamic Networks

Abstract

The Distributed Trigger Counting (DTC) problem is a fundamental block for many distributed applications. Such a problem is to raise an alert while the whole system receives a pre-defined number of triggers. There have been several algorithms proposed to solve the DTC problem in the literature. However, these existing algorithms are all under the assumption that there is no event regarding process moving, leaving and joining in the network. In other words, they can be only applicable to static networks. The foregoing assumption is not practical for dynamic networks with continually changing topology. In this paper, we investigate the DTC problem for dynamic networks and introduce a distributed algorithm without any global assumption. Moreover, to reduce the message complexity of the above algorithm, we further propose a more message-efficient version, only with one additional requirement that all processes have learned ahead the upper bound on number of processes involved in the computation.