Detecting Unstable Conjunctive Locality-Aware Predicates in Large-Scale Systems

Abstract

Recently, the concept of locality-aware predicates (LAP) has been proposed. A LAP models a predicate within a local region of the whole network in a large-scale locality driven system, such as WSNs and modular robotics. In such systems, the cost of doing a global predicate detection is high, besides which, a predicate over the state of a local region better captures properties of local interactions. Thus, LAP detection becomes a relevant and interesting problem. In this paper, we explore the problem of detecting unstable conjunctive LAP, and develop a scale-free algorithm by running an interval-based detection algorithm using a vector clock built on-the-fly for processes in the local region. More importantly, we develop the encoded vector clock (EVC) technique. EVC makes detecting unstable conjunctive LAP more practical in large-scale systems by reducing the storage cost.