Predicate Detection in Large-Scale Locality-Driven Networks

Global predicate detection is an important problem in many distributed systems. It aims at detecting whether a certain distributed property has been satisfied during the system execution. The traditional detection algorithms are based on logical clocks. They explore the causal relationship between events occurring during the system execution. However, this makes these algorithms not suitable to detect global properties in physical time. Furthermore, in arising new types of distributed systems, such as wireless sensor networks and modular robotics, where events are locality driven and the scale of the system is large with individual process having limited computation resources, the traditional algorithms simply cannot handle the complexities. To address these issues, we first propose the concept of locality-aware predicate (LAP) which aims at detecting predicates within a local region. Although a LAP is defined only within a local region, observing the local area consistently requires considering the entire system in a consistent manner. This raises the challenge of making the complexities of the corresponding detection algorithms scale-free. We design algorithms for detecting both stable and unstable LAPs and show that they are scale-free. We also propose the methodology of hierarchical repeated detection. This approach of detecting predicates relies only on neighborhood communication to collaboratively detect global predicates. Compared with the traditional detection algorithms, hierarchical detection incurs a much smaller cost which is distributed across the entire system, and is capable of continuing the detection even when individual node crashes during the detection. The performance evaluation of our proposed algorithm shows its great potential for detecting predicates in networks where individual process only has limited resources and is prone to crash failure. Furthermore, we propose the Instantaneously detection algorithm which is built on top of the hierarchical detection methodology. We combine several approximation techniques with the hierarchical detection method to make the algorithm capable of detecting predicates in physical time even when synchronized physical clock is not available in the system. Since the detection is achieved via neighborhood communication only, this algorithm can detect predicates in physical time with a high accuracy while still relies solely on logical clocks.