Show simple item record

dc.contributor.authorStoller, Scott D.en_US
dc.contributor.authorSchneider, Fred B.en_US
dc.description.abstractA new algorithm is presented for detecting whether a particular computation of an asynchronous distributed system satisfies $\Poss\Phi$ (read "possibly $\Phi$"), meaning the system could have passed through a global state satisfying $\Phi$. Like the algorithm of Cooper and Marzullo, $\Phi$ may be any global state predicate; and like the algorithm of Garg and Waldecker, $\Poss\Phi$ is detected quite efficiently if $\Phi$ has a certain structure. The new algorithm exploits the structure of some predicates $\Phi$ not handled by Garg and Waldecker's algorithm to detect $\Poss\Phi$ more efficiently than is possible with any algorithm that, like Cooper and Marzullo's, evaluates $\Phi$ on every global state through which the system could have passed. A second algorithm is also presented for off-line detection of $\Poss\Phi$. It uses Strassen's scheme for fast matrix multiplication. The intrinsic complexity of off-line and on-line detection of $\Poss\Phi$ is discussed.en_US
dc.format.extent242553 bytes
dc.format.extent259054 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleFaster Possibility Detection by Combining Two Approachesen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record