A Dynamic Distributed Algorithm for Read Write Locks

In this paper, a new algorithm that extends Naimi-Trehel token-based mutual exclusion is proposed. Contributions are twofold. First, our algorithm evolves within an changing environment, processes can join and leave the system while the "parent" tree is in ongoing transformation and, while requests accessing the critical section are inserted. Both the tree structure and the original algorithm are amended. We impose new rules and add new variables to the original structure, so as to maintain the connectivity of the "parent" tree as well as the "next" chain, whatever circumstances. Second, the possibility to share the token between processes is introduced. This allows either multiple concurrent readers or a single writer to enter the critical section. In the "next" chain of successive readers, a newly introduced "read handler" ensures that all following requesters for read access may enter the critical section simultaneously, and keeps the token as long as at least one reader is in the critical section. In all cases, our approach can be implemented such that it keeps an average complexity of O(log(n)) messages per request.