Affordable Access

Publisher Website

Two algorithms for mutual exclusion in real-time distributed computer systems

Authors
Journal
Journal of Parallel and Distributed Computing
0743-7315
Publisher
Elsevier
Publication Date
Volume
9
Issue
1
Identifiers
DOI: 10.1016/0743-7315(90)90114-5
Disciplines
  • Communication
  • Computer Science

Abstract

Abstract Two algorithms developed utilizing a priority-based event-ordering which manage mutual exclusion in distributed systems—computer networks—are proposed. In these systems, processes communicate only by messages and do not share memory. The computer network functions either (a) in an environment requiring priorities or (b) in a real-time environment. The algorithms are based on broadcast requests and token passing service approach, but the token need not be passed if no process wishes to enter the critical section. These algorithms are fully distributed and are insensitive to the relative speeds of node computers and communication links. They use only N messages per critical section, where N is the number of nodes (processes). The algorithms are optimal in the sense that a symmetrical, distributed algorithm cannot use fewer messages if requests are processed by each node computer concurrently. Both algorithms ensure freedom from starvation. There are mechanisms to handle node insertion and removal, node failure, the loss of the token, the existence of more than one token, and delivery of messages out of order.

There are no comments yet on this publication. Be the first to share your thoughts.