Predicate control for active debugging of distributed programs

Existing approaches to debugging distributed systems in-volve a cycle of passive observation followed by computa-tion replaying. We propose predicate control as an active approach to debugging such systems. The predicate control approach involves a cycle of observation followed by con-trolled replaying of computations, based on observation. We formalize the predicate control problem for both off-line and on-line scenarios. We prove that off-line predicate control for general boolean predicates is NP-hard. How-ever, we provide an efficient solution for off-line predicate control for the class of disjunctive predicates. We further solve on-line predicate control for disjunctive predicates under certain restrictions on the system. Lastly, we demonstrate how both off-line and on-line predicate control facilitate distributed debugging by allow-ing the programmer to control computations to maintain global safety properties. 1