Deriving a distributed deadlock detection algorithm from knowledge transitions

Date of Publication

1999

Document Type

Master's Thesis

Degree Name

Master of Science in Computer Science

Subject Categories

Computer Sciences

College

College of Computer Studies

Department/Unit

Computer Science

Thesis Adviser

Philip Chan

Defense Panel Chair

Caslon L. Chua

Defense Panel Member

Merlin Cruz

Teresita Limoanco

Abstract/Summary

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.

Abstract Format

html

Language

English

Format

Print

Accession Number

TG02950

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

viii, 89, [3] leaves ; 28 cm.

Keywords

Computer algorithms; Distributed operating systems (Computers); Programming (Electronic computers)

This document is currently not available here.

Share

COinS