Self-stabilizing deadlock algorithms in distributed systems

A self-stabilizing system is a network of processors, which, when started from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite number of steps. Self-stabilization is an evolving paradigm in fault-tolerant computing. This research will be the first time self-stabilization is used in the areas of deadlock detection and prevention. Traditional deadlock detection algorithms have a process initiate a probe. If that probe travels around the system and is received by the initiator, there is a cycle in the system, and deadlock is detected. In order to prevent deadlocks, algorithms usually rank nodes in order to determine if an added edge will create a deadlock in the system. In a self-stabilizing system, perturbances are automatically dealt with. For the deadlock model, the perturbances in the system are requests and releases of resources. So, the self-stabilizing deadlock detection algorithm will automatically detect a deadlock when a request causes a cycle in the wait-for graph. The self-stabilizing prevention algorithm prevents deadlocks in a similar manner. The self-stabilizing algorithms do not have to be initiated by any process because the requests and releases create a perturbance which is dealt with automatically.

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of Nevada, Las Vegas

Year

1993

Author dc:creator

• Flatebo, Mitchell Elliott

Contributors dc:contributor

• Ajoy Kumar Datta

Statement dc:rights

• IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English

Identifier

https://oasis.library.unlv.edu/rtds/289

OAI identifier oai:identifier

oai:oasis.library.unlv.edu:rtds-1288