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

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.Abstract / p1 Contents / p5 1 Introduction / p13 1.1 The Mutual Exclusion Problem / p13 1.2 Distributed Systems / p14 1.3 The Distributed Mutual Exclusion Problem / p15 1.4 The Distributed k-Mutual Exclusion Problem / p15 1.5 Fault Tolerance of Distributed Systems / p16 1.6 Organization of This Dissertation / p16 I The Coterie Approach / p19 2 The Coterie Approach for the Distributed k-Mutual Exclusion / p21 2.1 Previous Works for the Distributed 1-Mutual Exclusion / p21 2.2 Previous Works for the Distributed k-Mutual Exclusion / p25 2.3 Models and k-Coteries / p26 3 Availability of k-Coterie / p31 3.1 Assumptions and Definitions / p31 3.2 k-Majority Coteries / p33 3.3 k-Singleton Coteries / p37 3.4 Concluding Remarks / p37 4 A Distributed k-Mutual Exclusion Algorithm using k-Coterie / p39 4.1 The Distributed k-Mutual Exclusion Algorithm / p39 4.2 Correctness proofs / p41 4.3 Message complexity / p43 4.4 Concluding Remarks / p43 5 Experimental Evaluation of the k-Mutual Exclusion Algorithm / p45 5.1 Assumptions and the Simulation Model / p45 5.2 Outline of the Simulation System / p46 5.3 The Distributed k-Mutual Exclusion Algorithm by Kerry Raymond / p48 5.4 Simulation and Results / p48 5.5 Concluding Remarks / p55 II The Self-Stabilization Approach / p57 6 The Self-Stabilization Approach for the Distributed k-Mutual Exclusion / p59 6.1 Computational Models / p59 6.2 Previous Works / p61 6.3 Preliminaries / p62 7 Self-Stabilizing Mutual Exclusion Algorithms / p67 7.1 Self-Stabilizing k-Mutual Exclusion Algorithms / p67 7.2 A Self-Stabilizing 1-Mutual Exclusion Algorithm with Randomization / p79 7.3 Concluding Remarks / p90 8 Conclusion / p91 A Local Coteries and a Distributed Resource Allocation Algorithm / p93 A.1 The Resource Model / p94 A.2 The Resource Allocation Problem / p94 A.3 Local Coteries / p95 A.4 A Distributed Resource Allocation Algorithm / p96 A.5 Correctness Proof / p99 A.6 Concluding Remarks / p102 B Implementations of Distributed k-Mutual Exclusion Algorithms / p103 B.1 Our Distributed k-Mutual Exclusion Algorithm using k-Coterie / p104 B.2 Raymond's Distributed k-Mutaul Exclusion Algorithm / p108 B.3 The Behavior of a Process / p110広島大学(Hiroshima University)博士(工学)Engineeringdoctora