Ha Sook Jeong, Bae Ihn Han

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 4, No. 9, pp. 2221-2234, Sep. 1997
10.3745/KIPSTE.1997.4.9.2221,   PDF Download:

Abstract

Distributed mutual exclusion algorithms have employed two approaches to achieve mutual exclusion and can be divided into two broad classes : token-based and permission-based. Token-based algorithms share a unique token among the nodes and a node is allowed to access its common resources if it possesses the token. Permission-based algorithms require one of more successive rounds of message exchanges among the nodes to obtain the permission to access the common resources. A hypercube architecture has earned wide acceptance in multiprocessor systems in the past few years because of its simple, yet rich topology. Accordingly, we study distributed permission-based mutual exclusion algorithms for hypercubes, and design a distributed permission-based mutual exclusion algorithm based on a new information structure adapted to the hypercubes. The new information structure is a request set of T-pattern from a logical mesh that is embedded into a hypercube. If a node wants to access the common resources, it sends request message to all nodes in the request set by Lan's multicast algorithm. Once the node receives a grant message from all nodes in the request set, it accesses the common resource. We evaluate our algorithm with respect to minimum round-trip delay, blocking delay, and the number of messages per access to the common resource.

Statistics
Cite this article