Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/846
Title: An efficient distributed mutual exclusion algorithm based on relative consensus voting
Authors: Cao, J 
Zhou, J
Chen, D
Wu, J
Keywords: Algorithms
Computational methods
Computer simulation
Problem solving
Synchronization
Topology
Issue Date: 2004
Publisher: IEEE Computer Society
Source: IPDPS 2004 : 18th International Parallel & Distributed Processing Symposium : 26-30 April 2004, Santa Fe, New Mexico, p. 711-720 How to cite?
Abstract: Many algorithms for achieving mutual exclusion in distributed computing systems have been proposed. The three most often used performance measures are the number of messages exchanged between the nodes per Critical Section (CS) execution, the response time, and the synchronization delay. In this paper, we present a new fully distributed mutual exclusion algorithm. A node requesting the CS sends out the request message which will roam in the network The message will be forwarded among the nodes until the requesting node obtains enough permissions to decide its order to enter the CS. The decision is made by using Relative Consensus Voting (RCV), which is a variation of the well-known Majority Consensus Voting (MCV) scheme. Unlike existing algorithms which determine the node to enter the CS one by one, in our algorithm, several nodes can be decided and ordered for executing the CS. The synchronization delay is minimal. Although the message complexity can be up to O(N) in the worst case in a system with N nodes, our simulation results show that, on average, the algorithm needs less number of messages and has less response time than most of those existing algorithms which do not require a logical topology imposed on the nodes. This is especially true when the system is under heavy demand. Another feature of the proposed algorithm is that it does not require the FIFO property of the underlying message passing mechanism.
URI: http://hdl.handle.net/10397/846
ISBN: 0-7695-2132-0
Rights: © 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Appears in Collections:Conference Paper

Files in This Item:
File Description SizeFormat 
consensus-voting_04.pdf187.68 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

4
Last Week
0
Last month
1
Citations as of Nov 16, 2017

Page view(s)

324
Last Week
1
Last month
Checked on Nov 19, 2017

Download(s)

579
Checked on Nov 19, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.