Efficient Algorithms for Predicate Detection using Hybrid Logical Clocks
Sorrachai Yingchareonthawornchai, Vidhya Tekken Valapil, Sandeep S. Kulkarni, Eric K. Torng, Murat Demirbaş · 2017
Predicate detection is a critical aspect in debugging and monitoring of distributed systems. Runtime monitoring of distributed systems should satisfy two main requirements: wait-free execution and efficient computation. Monitoring is wait-free if it is non-intrusive (application being monitored is not stopped due to monitoring) and is efficient if the monitoring overhead is small. We define a monitor to be ϵ-sensitive if it is guaranteed to detect all predicates that are true for at least an ϵ time interval in true physical time. We focus on using hybrid logical clocks (HLCs) to perform wait-free and efficient predicate detection. HLC uses only constant space, has no false positives, and is 2ϵ-sensitive where e is the synchronization error bound. We focus on developing efficient algorithms for detecting weak conjunctive predicates (WCPs) with the help of HLC and then extend them to detect arithmetic predicates such as those necessary for expressing resource usage, network density, and so on.