Siphon-based deadlock detection in Integrated Model of Distributed Systems (IMDS)
Wiktor B. Daszczuk · Annals of Computer Science and Information Systems · 2018
Integrated Model of Distributed Systems (IMDS) is a formalism for specification and verification of distributed systems, especially following IoT (Internet of Things) paradigm.The formalism emphasizes such features as asynchrony of actions and communication, locality of decisions, and autonomy in executing actions.In conjunction with model checking, IMDS allows to analyze such features of distributed systems as deadlocks or distributed termination.However, the nature of model checking allows to find one deadlock in a single run of the verifier, which produces a counterexample.The conversion of IMDS specification to a Petri net is used to identify multiple deadlocks in one verification, using siphons.Model checking is used to verify if a siphon can become empty, which denotes a true deadlock in a purely cyclic system, like FMS (Flexible Manufacturing Systems).The extension of the verification by temporal checking allows to cover systems with any structure: cyclic, terminating, or with a more complex scheme.In addition, the proposed procedure allows to easily identify processes participating in partial deadlocks.Two types of deadlock can be identified: communication deadlocks and resource deadlocks.