PBCBT: AN IMPROVEMENT OF NTBCBT ALGORITHM

The classic mutual exclusion problem in distributed systems occurs when only one process should access a shared resource. Various algorithms are proposed in order to solve this problem. When using a permission based approach which consist in exchanging permission messages to grant access to the critical resource, less messages should be sent over the network because bandwidth consumption and synchronization delay should be reduced. Richa, shikha and Pooja proposed an algorithm using nodes logically organized in a complete binary tree. This algorithm called NTBCBT requires 4log2(N) messages per access to critical section and a synchronization delay of 3log2(N) for a set of N nodes competing for the critical ressource. In this paper, we study NTBCBT and we show that this algorithm has problems related with safety, liveness and scheduling. We improve this algorithm by correcting these weaknesses. Moreover, our algorithm requires 3log(N) messages per access to critical section and a synchronization delay of 2log(N). This improvement is due to the removal of useless messages, a reorganization of instructions on each node and an insertion of access requests using their timestamp