Distributed Mutual Exclusion Based on Causal Ordering

Abstract

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 P_i requested the critical section before a process P_j, then the process P_i will enter its critical section before the process P_j. 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.