Paper Info
Title
Deadlock Detection of EFSMs Using Simultaneous Reachability Analysis
Abstract
Simultaneous reachability analysis (SRA) is a recently proposed technique to alleviate the state space explosion problem in reachability analysis of concurrent systems. Its goal is to reduce the number of generated states while guaranteeing the detection of certain types of faults in the system such as deadlock and unexecutable transitions. The main idea of SRA is to allow a global transition in a reachability graph to contain a set of local transitions (i.e. transitions of individual processes) such that the state reached by the global transition is independent of the execution order of the associated local transitions.In this paper, we show how to apply the SRA approach to systems modeled as extended finite state machines (EFSMs) with multiple ports. Empirical results from applying our SRA algorithm to the dining philosophers problem indicate that our algorithm reduces the number of generated states and the computation time by about 90%.
Year
DOI
Venue
2000
10.1109/ICDSN.2000.857555
DSN
Keywords
Field
DocType
simultaneous reachability analysis,reachability analysis,sra approach,local transition,state space explosion problem,sra algorithm,dining philosophers problem,deadlock detection,global transition,reachability graph,extended finite state machine,computer science,protocols,system modeling,race conditions,efsm,finite state machines,parallel programming,concurrency control,testing,topology,fault detection,scalability
Concurrency control,Computer science,Deadlock,Algorithm,Extended finite-state machine,Real-time computing,Finite-state machine,Reachability,Deadlock prevention algorithms,State space,Distributed computing,Dining philosophers problem
Conference
ISBN
Citations 
PageRank 
0-7695-0707-7
3
0.45
References 
Authors
10
3
Name
Order
Citations
PageRank
Bengi Karaçali1222.27
Kuo-chung Tai21274132.89
Mladen A. Vouk345249.92