Generalized fair reachability analysis for cyclic protocols with nondeterministic and internal transitions

摘要

In this paper, we extend the generalized fair reachability notion to cyclic protocols with nondeterministic and internal transitions. By properly incorporating internal transitions into the formulation of fair progress vectors, we prove that with only a few modifications, all the results established for cyclic protocols without nondeterministic and internal transitions still hold even if nondeterministic and internal transitions are allowed. We identify indefiniteness as a new type of logical error resulting from reachable internal execution cycles and show that it can also be detected for the class of cyclic protocols with finite fair reachable state spaces with finite extension.