A Study on Distributed k-Mutual Exclusion Algorithms

分散k-相互排除アルゴリズムに関する研究

Kakugawa Hirotsugu

The mutual exclusion problem is a problem of arbitrating access conflicts for resources. The problem has been considered as a fundamental problem in computer science and extensively studied from the first minute operating systems started providing multi-tasking or multi-programming feature. Recently, a large number of computers are connected to a computer network. Such a system is called a distributed system. In a distributed system. several processes do their jobs by communicating with other processes on remote computers. When they share resources, processes may request the same resource at the same time. If the resource requires mutually exclusive access, then some regulation is needed to access it. This is the distributed mutual exclusion problem.

Most of previous works for the distributed mutual exclusion problem treat the case in which only one resource exists in a distributed system. This model may be suitable for modeling, e.g.. access control of a distributed database. However, there are other cases in which more than one identical resources exist in a distributed system. The problem of arbitrating identical k resources is called the distributed k-mutual exclusion problem.

Distributed systems consist of many components such as computers and communication links. In general, the probability that all components are simultaneously in operational is smaller than the probability that a component is in operational. This implies that when we design a distributed system, we should expect that sonic components may fail. Fault tolerance is therefore regarded as one of time most important. issues in designing distributed systems. Unlike parallel computers. distributed systems are loosely coupled, so that it is easy to add redundant components to increase the availability of distributed systems in such a way that even if several computers and/or communication links may fail, the rest of system is still in operational and alive components work correctly.

This dissertation investigates the distributed k-mutual exclusion problems. We discuss two approaches: the coterie approach and the self-stabilization approach. In Chapter 1. we give a general introduction to the distributed k-mutual exclusion problem. and address the objectives of this dissertation.

Part I contains the coterie approach. In Chapter 2. we give an introduction to the coterie-based distributed mutual exclusion and introduce the concept of k-coterie as an extension of coterie. In Chapter 3. the availability of k-coterie is investigated. In Chapter 4, a distributed k-mutual exclusion algorithm using k-coterie is proposed and its correctness is proven. In Chapter 5, to demonstrate the efficiency of the proposed algorithm, computer simulations of the proposed algorithm are done.

In Part II, the self-stabilization approach is discussed. A self-stabilizing system is a system which converges to a legitimate (stable) system state without centralized control even if any transient errors happen. In Chapter 6, we give an introduction to the self-stabilization approach. Formal definitions of computational models are described. In Chapter 7 we propose several self-stabilizing mutual exclusin algorithms. Forst, we propose a self-stabilizing k-mutual exclusion algorithm for unidirectional and bidirectional ring networks whose sizes are prime. The proposed algorithm does not require process identifiers. i.e., it is a uniform system. Thus, it works for anonymous ring networks. Next, we investigate the self-stabilizing 1-mutual exclusion problem as a special case of the self-stabilizing k-mutual exclusion problem. We propose a randomized self-stabilizing 1-mutual exclusion algorithm for unidirectional ring networks.

In Chapter 8, we summlize the results in this dissertation and discuss future tasks.

Electrical engineering [ 540 ]

eng

Copyright(c) by Author

広島大学