Title

Tree-based distributed algorithm for the K-entry critical section problem

Abstract

In this paper, we present a token-based algorithm for solving the K-entry critical section problem. Based on Raymond's tree-based approach [4], we regard the nodes as being arranged in a directed tree structure, and all messages used in the algorithm are sent along the directed edges of this tree. There are K tokens in the system; we use a bag structure at each node to record the collection of the neighboring nodes, possibly with multiple occurrences of the same node, through which the K tokens can be located. As a result, there are K paths from each node leading to the K tokens in the system. Our algorithm requires at most 2KD messages for a node to enter the CS, where D is the diameter of the tree. Therefore, when the diameter D is much smaller than N, the number of nodes, e.g. D = O(1) as in a star or D = O(logN) as in a binary tree, our algorithm's upper bound on the number of messages per CS is smaller than those reported in [15,19].

Publication Date

12-1-1994

Publication Title

Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS

Number of Pages

592-597

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

Socpus ID

0028749077 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0028749077

This document is currently not available here.

Share

COinS