Journal of Computer Science

Distributed Mutual Exclusion Based on Causal Ordering

Mohamed Naimi and Ousmane Thiare

DOI : 10.3844/jcssp.2009.398.404

Journal of Computer Science

Volume 5, Issue 5

Pages 398-404


Problem statement: Causality among events, more formally the causal ordering relation, is a powerful tool for analyzing and drawing inferences about distributed systems. The knowledge of the causal ordering relation between processes helps designers and the system itself solve a variety of problems in distributed systems. In distributed algorithms design, such knowledge helped ensure fairness and liveness in distributed algorithms, maintained consistent in distributed databases and helped design deadlock-detection algorithm. It also helped to build a checkpoint in failure recovery and detect data inconsistencies in replicated distributed databases. Approach: In this study, we implemented the causal ordering in Suzuki-Kasami’s token based algorithm in distributed systems. Suzuki-Kasami’s token based algorithm in distributed algorithm that realized mutual exclusion among n processes. Two files sequence numbers were used one to compute the number of requests sent and the other to compute the number of entering in critical section. Results: The causal ordering was guaranteed between requests. If a process Pi requested the critical section before a process Pj, then the process Pi will enter its critical section before the process Pj. Conclusion: The algorithm presented here, assumes that if a request req was sent before a request req’s, then the request req will be satisfied before req’s.


© 2009 Mohamed Naimi and Ousmane Thiare. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.