Show simple item record

dc.contributor.authorStoller, Scott D.en_US
dc.contributor.authorSchneider, Fred B.en_US
dc.date.accessioned2007-04-23T18:02:07Z
dc.date.available2007-04-23T18:02:07Z
dc.date.issued1995-04en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1511en_US
dc.identifier.urihttps://hdl.handle.net/1813/7168
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.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
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

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics