Deriving a distributed deadlock detection algorithm from knowledge transitions

This study is concerned with the derivation of a deadlock detection algorithm for distributed systems from a knowledge-base logic called knowledge transitions. It starts with discussions concerning deadlock and the problem of detecting deadlock in distributed systems. This is followed by a review of existing algorithms for handling the deadlock problem, in particular, deadlock detection in distributed systems. The concepts of knowledge in distributed systems, knowledge transitions and the principle of communication closed layers are presented as the theoretical foundations of the study. The technique of layering by knowledge transitions in the design of distributed algorithms is also presented basically for being the fundamental method used in the derivation of the algorithm. The actual derivation of the algorithm is presented with slight modifications of the approach suggested in [JANS94a]. The derivation starts with the initial design specifications and requirements, and then followed by some refinements using layers and knowledge transitions. This is followed by the implementation of the layers and transitions into algorithms and then combined together into a sequentially layered composition taking into consideration communication closedness between layers. Finally this is transformed into an implementable parallel and distributed composition using one of the laws of communication closed layers