检索结果-内蒙古大学图书馆

A simple token-based algorithm for the mutual exclusion problem in distributed systems

JOURNAL OF SUPERCOMPUTING 2017年第9期73卷 3861-3878页

作者： Neamatollahi, Peyman Sedaghat, Yasser Naghibzadeh, Mahmoud Ferdowsi Univ Mashhad Dept Comp Engn Fac Engn Mashhad Iran

Solving the problem of mutually exclusive access to a critical resource is a major challenge in distributed systems. In some solutions, there is a unique token in the whole system which acts as a privilege to access a critical resource. Practical and easily implemented, the token-ring algorithm is one of the most popular token-based mutual exclusion algorithms known in this field's literature. However, it suffers from low scalability and a high average waiting time for resource seekers. The present paper proposes a new algorithm which employs a two-dimensional torus logical structure of N processes and the token-ring algorithm concept. It performs in a way that increasingly raises scalability and reduces the average waiting time of the token-ring algorithm. The token makes a circular movement along the columns of the two-dimensional torus (vertical ring), while the requests for the critical resource make a circular movement along the rows of the torus (horizontal ring). In this algorithm, the number of messages exchanged is between and 3 under light load situations and, under heavy load situations, is at the most three messages per critical section invocation. Thus, in contrast with the leading algorithms, the proposed algorithm has gained significant improvements, in addition to having been proved to operate correctly.

关键词： Mutual exclusion Critical section Distributed systems token-based algorithm token-ring

来源：评论

学校读者我要写书评

暂无评论

A hybrid token-based distributed mutual exclusion algorithm using wraparound two-dimensional array logical topology

引用

INFORMATION PROCESSING LETTERS 2011年第17期111卷 841-847页

作者： Taheri, Hoda Neamatollahi, Peyman Naghibzadeh, Mahmoud Islamic Azad Univ Mashhad Branch Dept Comp Engn Mashhad Iran Ferdowsi Univ Mashhad Fac Engn Dept Comp Engn Mashhad Iran

In token-based distributed mutual exclusion algorithms a unique object (token) is used to grant the right to enter the critical section. For the movement of the token within the computer network, two possible methods can be considered: perpetual mobility of the token and token-asking method. This paper presents a distributed token-based algorithm scheduling mutually exclusive access to a critical resource by the processes in a distributed network. This network is composed of N nodes that communicate by message exchanges. The proposed hybrid algorithm imposes a logical structure in the form of wraparound two-dimensional array on the network. It applies the concept of perpetual mobility of the token in columns and token-asking in rows of the array. The major purpose of the algorithm is to increase the scalability property and decrease overhead due to additional communication in a system with at least one unresponded critical section request at any given time. In this status, typically, the number of message exchanges is between root N and 2 root N under light demand and reduces to root N message exchanges under heavy demand. Therefore, it outperforms lots of well known algorithms in terms of number of messages exchanged. The algorithm satisfies safety and liveness properties. (C) 2011 Elsevier B.V. All rights reserved.

关键词： token-based algorithm Mutual exclusion Distributed systems Hybrid algorithm Concurrency Message exchange

来源：评论

学校读者我要写书评

暂无评论

A priority-based distributed group mutual exclusion algorithm when group access is non-uniform

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2007年第7期67卷 797-815页

作者： Mittal, Neeraj Mohan, Prajwal K. Univ Texas Dept Comp Sci Richardson TX 75083 USA Intel Corp Digital Home Grp Hillsboro OR 97124 USA

In the group mutual exclusion problem, each critical section has a type or a group associated with it. Processes requesting critical sections belonging to the same group (that is, of the same type) may execute their critical sections concurrently. However, processes requesting critical sections belonging to different groups (that is, of different types) must execute their critical sections in a mutually exclusive manner. Most algorithms for solving the group mutual exclusion problem that have been proposed so far in the literature treat all groups equally. This is quite acceptable if a process, at the time of making a request for critical section, selects a group for the critical section uniformly. However, if some groups are more likely to be selected than others, then better performance can be achieved by treating different groups in a different manner. In this paper, we propose an efficient algorithm for solving the group mutual exclusion problem when group selection probabilities are nonuniformly distributed. Our algorithm has a message complexity of 2n - 1 per request for critical section, where n is the number of processes in the system. It has low synchronization delay of one message hop and low waiting time of two message hops. The maximum concurrency of our algorithm is n, which implies that if all processes have requested critical sections of the same type then all of them may execute their critical sections concurrently. Finally, the amortized message-size complexity of our algorithm is O(1). Our experimental results indicate that our algorithm outperforms the existing algorithms, whose complexity measures are comparable to that of ours, by as much as 50% in some cases. (C) 2007 Elsevier Inc. All rights reserved.

关键词： message-passing system resource management group mutual exclusion token-based algorithm non-uniform group selection priority-based scheme

来源：评论

学校读者我要写书评

暂无评论

Distributed mutual exclusion algorithms for grid applications: A hierarchical approach

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第1期66卷 128-144页

作者： Bertier, M Arantes, L Sens, P Inst Natl Rech Informat & Automat INSA F-35042 Rennes France Univ Paris 06 LIP6 F-75252 Paris 05 France INRIA Rocquencourt F-75252 Paris 05 France

The majority of current distributed mutual exclusion algorithms are not suited for parallel or distributed applications on a Grid as they do not consider the heterogeneity of latency on Grids. We propose two distributed mutual exclusion algorithms, based on Naimi-Trehel's token-based algorithm, which take into account latency gaps, especially those between local and remote clusters of machines. Our first algorithm exploits cluster locality by giving higher priority to critical section requests issued from nodes of the same cluster when compared to those from remote nodes. Our second algorithm adds a router layer to the first algorithm, bringing it closer to Grid network topology. Viewing each cluster as a single node, the Naimi-Trehel algorithm is applied to this router layer. Redirection of inter-cluster messages to cluster's nodes is then minimized. (c) 2005 Elsevier Inc. All rights reserved.

关键词： distributed mutual exclusion algorithms token-based algorithm grid latency heterogeneity cluster locality

来源：评论

学校读者我要写书评

暂无评论

Info-based approach in distributed mutual exclusion algorithms

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第5期72卷 650-665页

作者： Neamatollahi, Peyman Taheri, Hoda Naghibzadeh, Mahmoud Islamic Azad Univ Mashhad Branch Dept Comp Engn Mashhad Iran Ferdowsi Univ Mashhad Fac Engn Dept Comp Engn Mashhad Iran

In this paper, we propose a token-based fully distributed algorithm with token-asking method for Distributed Mutual Exclusion (DME) in a computer network composed of N nodes that communicate by message exchanges. The main goal is to introduce a new class of token-based DME algorithms called info-based algorithms. In some previous algorithms, the request to enter a critical section is sent to all nodes because the token-holding node is unknown, but in this info-based algorithm some nodes know the token-holding node and lead critical section entering requests to it, directly. This algorithm uses a logical structure in the form of a wraparound two-dimensional array which is imposed on the interconnecting network. Usually, a request message for entering the critical section is sent vertically down in the array, and eventually sent to the token-holding node with the assistant of an informed-node (common node between the row consisting of the token-holding node and the column consisting of the requester node). The nodes invoking the critical section can obtain the token with fewer message exchanges in comparison with many other algorithms. Typically, the number of message exchanges is 4 root N+1 under light demand which reduces to approximately 2 message exchanges under heavy demand. A correctness proof is provided. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Mutual exclusion Critical section Distributed systems token-based algorithm Message exchange Concurrency

来源：评论

学校读者我要写书评

暂无评论

Arbitration based Distributed Group Mutual Exclusion algorithm for Mobile Ad Hoc Networks 3

Arbitration Based Distributed Group Mutual Exclusion Algorit...

引用

International Conference Parallel Distributed Grid Computing

作者： Priya, Madhu Krishna, C. Rama Saini, Poonam NITTTR Dept CSE Chandigarh India PEC Univ Technol Dept CSE Chandigarh India

ISBN: (纸本)9781479976836

The group mutual exclusion problem is a simplification of mutual exclusion problem such that a set of processes in the similar group can enter a critical section all together. To handle group mutual exclusion, the interrelated solutions are chiefly classified into quorum-based, token-based as well as permission-based protocols. The proposed algorithm is based on tokens;a process that grasps a token can invoke a critical section. To our knowledge, only some algorithms have been proposed in the literature which follows permission-based or token-based approach. In this paper, we put the entire nodes into dissimilar regions. Arbitrator nodes have been introduced in this paper that forms the relationship among two neighboring regions. "Look-ahead" procedure is used which helps in dropping message complexity. We present the distributed group mutual exclusion algorithm developed for MANETs. The outcomes have been substantiated by simulations and experiments. We observed that the proposed algorithm outperforms the TQGmx algorithm in performance parameters such as synchronization delay, response time in addition to message complexity.

关键词： Group Mutual Exclusion (GME) Mobile Ad hoc Networks token-based algorithm Look-ahead Method

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：