Skip to Main content Skip to Navigation
Conference papers

A Robust Permission-Based Hierarchical Distributed k-Mutual Exclusion Algorithm

Abstract : Distributed mutual exclusion is a basic building block of distributed systems that coordinates the access to critical shared resources. This work introduces a novel permission-based k-mutual exclusion algorithm for distributed systems with crash faults. Processes monitor each other and organize themselves on an adaptive virtual topology that is based on the hypercube and presents several logarithmic properties. Mutual exclusion is deployed on top of this monitoring system. Processes communicate through spanning trees which are created with a fully distributed strategy that tolerates faults by using process state information provided by the underlying monitoring system. Both the mutual exclusion and the distributed spanning tree algorithm are formally specified. The strategy is proven to guarantee the safety and liveness of the concurrent access of n processes to k critical resources. Experimental results are presented, showing that the algorithm performs efficiently even when up to n-1 processes are faulty.
Complete list of metadata

https://hal.inria.fr/hal-00931856
Contributor : Pierre Sens <>
Submitted on : Wednesday, January 15, 2014 - 11:35:01 PM
Last modification on : Friday, January 8, 2021 - 5:46:03 PM

Identifiers

Citation

Luiz Rodrigues, Jaime Cohen, Luciana Arantes, Elias Duarte Júnior. A Robust Permission-Based Hierarchical Distributed k-Mutual Exclusion Algorithm. The 12th International Symposium on Parallel and Distributed Computing, Jun 2013, Bucharest, Romania. pp.151-158, ⟨10.1109/ISPDC.2013.28⟩. ⟨hal-00931856⟩

Share

Metrics

Record views

323