Detecting Tree Distributed Predicates

Abstract

In a large-scale locality-driven network, knowing the state of a local area is sometimes necessary due to either interactions being local and driven by neighborhood proximity or the users being interested in the state of a certain region. We propose locality-aware predicates that aim at detecting a predicate within a specified area. We model the area of interest as the set of processes that are within distance k from the initiator process. By associating the predicate with a tree topology, we force the set of processes satisfying the predicate to form a tree with height no more than k. This enables the detection of the predicate within the area of interest. We also formalize several classes of locality-aware predicates, which deal with strong stable and stable predicates for both conjunctive and relational types. The algorithms to detect each class are also proposed. These algorithms associate a tree topology constraint with the predicate to be detected. Since a locality-aware predicate detects predicates only within the specified area, the complexities of the corresponding algorithms are thus scale-free. These properties make locality-aware predicate a natural fit for detecting distributed properties in systems such as modular robotics and wireless sensor networks.