DISTRIBUTED GROUPS MUTUAL EXCLUSION BASED ON DYNAMICAL DATA STRUCTURES
Ousmane Thiaré, Mohamed Naïmi, Abdelhak Mourad Gueroui, Ugb-Ufr Sat · 2009
ABSTRACT The group mutual exclusion (GME) problem is an interesting generalization of the mutual exclusion problem. Several solutions of the GME problem have been proposed for message passing distributed systems. In this paper we present a new Distributed Group Mutual Exclusion (DGME) based on Clients/Servers model, and uses a dynamic data structure. Several processes (Clients) can access simultaneously to a same opened session (Server). The algorithm ensures that, at any time, at most one session is opened, and any requested session will be opened in a finite time. The number of messages is between 0 and m, where m is the number of session in the network. In the average case, O(Log(m)) messages are necessary to open a session. The maximum concurrency is n, where n is the number of processes in the network. Keywords: Group Mutual Exclusion (GME), Client/Server 1. INTRODUCTION The mutual exclusion problem states that only a single process can be allowed to access in its critical section (CS). Hence, the mutual exclusion problems plays an important role in the design of computer systems. Several distributed systems are based on asynchronous messages passing, and without global clock. In the first class Permission-Based Algorithm (PBA) [3][7][10], where all involved processes vote to select one which receives the permission to access the CS. Lamport [9] was the first to design a fully distributed permission-based mutual exclusion algorithm using logical timestamps. In his algorithm each request set is the entire distributed system. Then, if n is the number of processes in the distributed system, the algorithm requires (n-1) request, (n-1) reply, and (n-1) releases. The algorithm requires 3(n-1) messages per critical section execution. Ricart and Agrawala [12] have reduced the number of messages in Lamport’s algorithm to 2(n-1). Carvalho and Roucairol’s algorithm [5] has further improved the number of messages in Ricart and Agrawala’s algorithm by avoiding some unnecessary request and reply messages. They have shown that the number of messages exchanged in their algorithm is between 0 and 2(n-1). Maekawa uses the number of message from O(n) to √n. In the second class, Token-Based Algorithms (TBA) [8][12], in which only one process, holding a special message called the token, may enter the critical section. The dynamical spanning tree is used in [13] to ensure the mutual exclusion. The reversal path permits to reduce the number of messages to Log(n) where n is the number of processes in the network. The performance metrics of the mutual exclusion algorithms are: the average number of messages necessary per critical section invocation, the response time, the fault tolerance. The mutual exclusion algorithm should be starvation-free, and fairness. The reversal path principle is used in [13] to solve the mutual exclusion problem in distributed system without logical time. The average number of messages needed per request is O(Log(n)), where n is the number of processes in networks. The rest of this paper is organized as follow: the principle of DGME is presented in the section 2. Section 3 describes the computational model assumed and we then present the algorithm. In section 4, we present an example. The section 5