Faster possibility detection by combining two approaches

A new algorithm is presented for detecting whether a particular computation of an asynchronous distributed system satisfies Poss Ф (read "possibly Ф”), meaning the system could have passed through a global state satisfying Ф. Like the algorithm of Cooper and Maxzullo, Ф may be any global state predicate; and like the algorithm of Gaxg and Waldecker, Poss Ф is detected quite efficiently if Ф has a certain structure. The new algorithm exploits the structure of some predicates not handled by Gaxg and Waldecker's algorithm to detect Poss cI, more efficiently than is possible with any algorithm that, like Cooper and Maxzullo's, evaluates Ф on every global state through which the system could have passed. A second algorithm is also presented for off-line detection of Poss Ф. It uses Strassen's scheme for fast matrix multiplication. The intrinsic complexity of off-line and on-line detection of Poss Ф is discussed.