AN IMPROVED ALGORITHM FOR PROTOCOL VALIDATION BY EXTENDED CIRCULAR EXPLORATION

In this paper, to improve the efficiency of state exploration and to relieve the problem of state explosion, we propose another method of state exploration called the extended circular exploration (ECE), which does not need to explore all the reachable global states and can be applied to N(N greater-than-or-equal-to 2)-party protocol with alternative routes, i.e. it is applicable to the protocol in which adaptive routing mechanism can be performed. Using this ECE, we can eliminate the topology restriction of the circular exploration (CE) through extending the notion of circular exploration. We explore only those global states which are reachable, provided that the participant processes of any group of transitions proceed at the same speed, and that they can be formed as a cycle. The state space thus explored is not exhaustive. The algorithm presented can detect deadlock error and unspecified reception error. It requires storage space and/or execution time much less than those of the conventional perturbation method. It can be viewed as a solution of the N-process collision and the interference mechanism.
Publisher
ELSEVIER SCIENCE BV
Issue Date
1993-09
Language
ENG
Keywords

PROGRESS STATE EXPLORATION; MACHINES

Citation

MICROPROCESSING AND MICROPROGRAMMING, v.36, no.4, pp.179 - 194

ISSN
0165-6074
DOI
10.1016/0165-6074(93)90242-D
URI
http://hdl.handle.net/10203/65652
Appears in Collection
CS-Journal Papers(저널논문)CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 161
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0