A Fault-Tolerant Strong Conjunctive Predicate Detection Algorithm for Large-Scale Networks

In large-scale networks where a continuously on-going monitoring program is needed, using traditional predicate detection algorithms might cause the system to have a single point of failure. This paper presents an on-line distributed algorithm that detects strong conjunctive predicates and we show that it is resilient to node failures. Our algorithm assumes a pre-constructed spanning tree in the system, and detects all satisfactions of the predicate in a hierarchical manner. Our algorithm is able to detect predicates at each level in the hierarchy, thus becoming resilient to node failures because of the capability to detect a partial predicate of the global predicate. This hierarchical detection manner also provides a finer-grained monitoring in those large-scale networks where grouping is established and the monitoring happens at the group level. Furthermore, comparing with other detection algorithms, our algorithm incurs a low space/time cost, which is distributed across all the nodes in the network, and a low message complexity. This makes our algorithm applicable in a resource-constraint network.