An improved √N algorithm for mutual exclusion in decentralized systems

Abstract An algorithm is proposed which realizes mutual exclusion in a computer network system where communications are conducted by messages only without using a shared memory. With this method, and by transferring a token representing the exclusion the exclusion right, the mutual exclusion is realized. A node wanting to execute a critical section first sends messages requesting exclusion to a set of nodes (members) assigned to it. The members keep this message, after receiving a finish exclusion message from some other node, transfer the exclusion request messages to the sender. The node receiving the token processes the critical section, and when finished, sends finish exclusion messages to the members. The members return information on nodes requesting exclusion known to them. According to this information, the next receiver of the token is determined. By contriving the selection of members and gathering information on nodes requesting exclusion, the mutual exclusion can be realized using √N + 1 or more but less than or equal to 3√N + 1 messages.