Generalized Fair Reachability Analysis for Cyclic Protocols with Nondeterminism and Internal Transitions

Loading...
Thumbnail Image
Files
CS-TR-3422.ps(208.89 KB)
No. of downloads: 94
CS-TR-3422.pdf(203.69 KB)
No. of downloads: 353
Publication or External Link
Date
1998-10-15
Authors
Liu, Hong
Miller, Raymond E.
Advisor
Citation
DRUM DOI
Abstract
In this paper, we extend the generalized fair reachability notion to cyclic protocols with nondeterminism and internal transitions. By properly incorporating internal transitions into the formulation of fair progress vectors, we prove that most of the results established for cyclic protocols without nondeterminism and internal transitions still hold even if nondeterminism and internal transitions are allowed. We identify indefiniteness as a new type of logical error resulting from reachable internal execution cycles and show that indefiniteness can also be detected for the class of cyclic protocols with finite fair reachable state spaces with finite extensions.
Notes
Rights